ABSTRACT. Less-than-truckload carriers need to consolidate where possible to save costs. Assuming that the paths shipments take are already predetermined, only two decisions can be made for shipments. The two decisions are hold or forward. If there is also a dynamic environment in which there is uncertainty, this decision becomes more difficult. We model the problem of holding or forwarding as a sequential decision process and use a rolling horizon approach. Two challenges arise. First, it must be possible to reach the global optimal solution. Second, this solution must also be found. For the first challenge we propose an algorithm, developed by us. For the second challenge we use a cost function approximation.

ABSTRACT. We consider a problem where customers dynamically request next-day home service, e.g., repair or installment. Different to attended home delivery, customers cannot select a time window (TW). Instead, the service provider assigns a next-day TW to each new requesting customer, if the customer can feasibly be inserted in the service route of the next day without violating the TWs of the existing customers. Else, the customer service is postponed to another day (which is outside of the scope of this work). For fast service and efficient operations, the provider aims on serving many customers the next-day. Thus, TWs have to be assigned that keep the fleet flexible for future requests. For such anticipatory assignments, we propose a scenario algorithm that sample a set of future request scenarios, solves the corresponding team orienteering problems (TOPs) with TWs, and uses the solutions to evaluate current TW-assignment decisions. One challenge is to set the TWs of the sampled customers in the scenarios. Setting them randomly leads to underestimation of the potential future services. Relaxing the TW-constraints leads to overly optimistic evaluations. Therefore, we create a compromise of both, assigning each sampled customer a carefully selected subset of TWs where service can take place. For real-time solutions of the TOP with multiple TWs, we propose to approximate its optimal solution value with a tight upper bound. The bound is obtained by solving the linear relaxation of a set packing reformulation via column generation. The feasibility of the assigned time window to the new customer is then assessed by solving a flow-based formulation with a branch-and-cut algorithm . We test our algorithm on artificial and Iowa City data. The results show that our method increases customer services significantly. We further show that our TW-compromise in the scenarios is crucial for successful decision making.

ABSTRACT. In intermodal transport, Service Network Design (SND) problems cover most tactical decisions of a carrier. Nevertheless, among the literature on SND, very few works include pricing decisions and the preferences of the shippers. In this study, we contribute to the existing body of knowledge by proposing a cycle-based formulation of the Service Network Design and Pricing (SNDP) problem which considers different aspects of the mode choice decisions of shippers. This formulation aims at finding the service’s itineraries, frequencies and prices that will maximize the profit of an intermodal carrier. Moreover, the mode choice preferences of shippers are modeled as a utility maximization accounting not only for the logistics costs, but also the frequency of the offered services and the accessibility of the transport mode. This bi-level formulation can be reformulated into a single level linear problem. The proposed model is compared to two other models (one cycled-based and one path-based) where shippers are purely cost minimizers. While the latter generate higher profits, they also result in unrealistic mode shares, with road transport being negligible. On the other hand, the proposed formulation leads to mode shares that are considerably closer to reality. In addition, higher revenues can be generated with a cycle-based formulation compared to a path-based as it allows for more consolidation opportunities for the carrier.

ABSTRACT. Drones have demonstrated potential to improve response to time-sensitive emergencies, such as out-of-hospital cardiac arrest (OHCA), which kills over 300,000 individuals in the US annually. Drones can facilitate early medical intervention by delivering an automated external defibrillator (AED) before ambulance arrival, but they require a willing bystander to apply the AED. Prior research on designing drone-enabled AED networks assumes that a bystander is always available at scene, although historical bystander participation is low. Therefore, these models may overestimate system performance and place drones in areas with low utilization. We introduce the concept of capturing bystander availability in joint location-queuing problems and propose a modeling framework to simultaneously optimize a drone-bystander-ambulance network for OHCA response. Service can be achieved by either an ambulance alone; or by the drone-delivered AED together with a bystander, complemented by a slower-arriving ambulance. We formulate this problem as a mixed-integer-linear program and use the solution structure to develop an accurate and highly scalable heuristic algorithm. We demonstrate our approach on a case study with three cities around Toronto, Canada. We find that even a small number of drones (e.g., five) improve response times by 15-20% and the fraction of calls served within 6 minutes by 27-61%. Models that assume instant bystander participation may overestimate the fraction of calls served within 6 minutes by up to 12-18% compared to those using realistic estimates. Simultaneously optimizing drone-bystander-ambulance networks pools ambulances in regions with low bystander availability, while using drones to cover the regions where ambulances are pooled from. Operationally, the drone-bystander-ambulance network is more effective in regions with limited ambulance resources or low ambulance availability. Adding a small number of drones may be more effective than adding many ambulances, especially in rural regions with lower incidence rates spread over large areas.

ABSTRACT. 1. Motivation In November 2022, Amazon announced Prime Air delivery services to customers liv- ing in California and Texas (https://www.aboutamazon.com/news/transportation/ amazon-prime-air-delivery-drone-reveal-photos). This service uses a new generation delivery drone, the MK30, exploiting a new drone technology offering several advantages in terms of flying range, temperature tolerance, safety-critical features, and a new capability to fly in light rain. This enables customers to choose drone delivery service even if they are located in “rural” areas. In fact, the new drones can operate longer distances safely by avoiding obstacles, thus allowing a complete delivery service without using trucks, as is done in the truck-drone delivery. This novel aspect motivated our study. In our pure drone delivery problem, we consider two logistics design features of a drone delivery system: the usage of swappable batteries and the customer service expressed in terms of travel time. The balanced use of batteries being assigned to the drones at the charging station is a tactical issue, while minimizing the overall travel time to serve the customers within their time windows is an operational aspect of the problem. Both are affected by uncertainty in the energy consumption of the drones during the trips, and in the customer locations and demands. To the best of our knowledge, the scientific literature is scarce of contributions devoted to pure drone delivery problems where tactical and operational aspects are faced together within an uncertain setting. Some pertinent problems focused on tactical drone problems are presented in Choi and Schonfeld (2017) and Troudi et al. (2018) that study the relation among battery capacity, payload, and flight range to determine the drone fleet size. Cheng and Rousseau (2020) formulate a multi-trip drone routing problem where energy consumption is modeled as a nonlinear function of payload and travel distance. Ulmer and Thomas (2018) model a truck-drone routing problem and consider random customer locations and demands.

2. Problem Description Our research project considers a big e-commerce player managing long-distance drone deliveries to meet the demand from random customers. The demand pattern and consumer service levels require the drones to make frequent stops to perform deliveries and to go back to the depot (or charging station) to perform full recharges. This implies a deterioration of the drone batteries. Moreover, uncertainty in energy consumption impacts time-to-delivery and the profitability of the service business. Our problem considers a set of batteries that need to be assigned to a set of drones to allow them to perform deliveries. Customer locations and demands are not known in advance and become available over time. The problem consists in designing a delivery plan that minimizes the total travel time and a charging plan ensuring that all batteries age equally. During the trips of the drones, their actual energy consumption is regularly observed, and if the energy level is too low, the drone might need to interrupt its trip and return preemptively to the depot.

3. Model formulation To represent the stochastic nature of the arrival of customer requests, we model the problem as a Markov decision process (MDP) over a finite, discrete-time horizon. An MDP is a stochastic framework consisting of stages (or epochs) for modeling sequential decision-making in the pres- ence of uncertainty. Specifically, we adopt a route-based MDP framework due to our problem’s characteristics (Ulmer et al. 2017) with the following components: • The (pre-decision) state of the system includes the information available to the decision-maker. For our problem, this includes the current time, the ordered set of outstanding customer locations scheduled for each drone, every drone’s routing plan starting from the charging station at the current time of day, the charge of the battery of each drone, and its capacity, the charge level of each battery at the charging station, the average time to recharge every battery fully, the number of times every battery has been swapped from the beginning of the time horizon, and the set of unsatisfied customer demands. • At a decision epoch, the decision-maker observes the state of the system, which captures all relevant information for making dispatching decisions. In this problem, a decision epoch occurs every t time units since the last decision epoch or when drones return to the depot for being rerouted. In the last case, a new battery assignment can be performed to these drones. • Based on the state at a decision epoch, the decision-maker selects an action, which consists of (i ) updating the routing of the drones (change the set of outstanding deliveries, reroute a drone to the depot, start new routes from the depot); and (ii ) deciding which batteries to assign to the drones at charging station. • The selected action incurs an immediate cost, and the combination of state and selected action results in a deterministic transition to a post-decision state. The immediate cost minimizes the aging of the batteries by avoiding unnecessary swaps and ensuring that batteries age equally. • Random information regarding customer demands arrive, resulting in a stochastic transition to the next pre-decision station. • Random information regarding the energy level of the flying drones is realized by the drones upon arrival at each node. The drone observes if its energy level is below a threshold established for each node of its trip and decides to either continue it or return to the depot preemptively.

4. Solution approach Let Π be the set of all Markovian deterministic policies, where a policy π ∈ Π is a sequence of decision rules π = (Xπ(s0), Xπ(s1), . . . , Xπ (sK)) where each decision rule Xπ(sk) : sk → X (sk) is a function that specifies the action choice when the process is at state sk and follows policy π. We seek a policy π ∈ Π that minimizes the total expected cost, conditional on the initial state. Identifying an optimal policy is challenging due to the three curses of dimensionality present in our problem. To address the fundamental challenge of estimating the cost-to-go for a current state, a Direct Lookahead (DL) model-based policy approximation is used, in which a dispatching time is consid- ered for the drones with fully recharged batteries at the charging station. The dispatching time accounts for new customer locations and demands that can reveal in the system. The uncertainty affecting the duration of the trips due to the random energy consumption is estimated on the basis of a lookup table of arc–load energy consumption. For each pair (arc, load) a random energy consumption er is computed by er = e + e × r, where e is the deterministic energy consumption and r is a random number extracted from a uniform distribution between −0.3 and 0.3. This table is built preemptively considering 30 different values of r, and it is used to approximate the energy consumption on the arcs that the drones are going to travel with their loads.

5. Computational experiments In our computational experiments, we use the instances from Ulmer and Thomas (2018) in mod- ified form to consider that only drones can perform the deliveries. Using a myopic heuristic as a benchmark, we use the set of instances to assess the design of the anticipatory solution approach. Table 1 shows the numerical results obtained through experiments on four classes of instances with a number of customers ranging from 37 to 170. Each line provides average computational results on 30 randomly generated energy consumption scenarios. Columns “total e” refer to the average energy consumption of the drones in kWh; columns “total t” report the average times in minutes to serve all the customers; columns “CPU(s)” show the average CPU time in seconds of the designed algorithms. The results obtained in the preliminary computational experiments

Table 1 Average computational results.

Anticipatory approach Myopic heuristic Instance total e total t(min) CPU(s) total e total t(min) CPU(s) BCCL 480 G 37 0.40 418.00 0.47 0.40 438.00 0.24 BCCL 480 G 69 0.41 430.00 0.86 0.44 440.00 1.09 BCCL 480 G 133 0.44 430.00 2.67 0.45 430.00 2.51 BCCL 480 G 170 0.44 420.00 4.44 0.44 430.00 3.96 Average 0.42 424.50 2.11 0.43 434.50 1.95

highlight the advantage of the anticipatory policy compared to the myopic one in terms of average time to serve the customers. The random energy consumption has a significant impact on large instances, while it is limited to those with a small number of customers, as we expected. Further computational experiments will be carried out to assess the performance of our method in terms of battery usage and swapping, routing plans, delivery costs, and delays.

References Cheng Y Cand Adulyasak, Rousseau LM (2020) Drone routing with energy function: Formulation and exact algorithm. Transportation Research Part B: Methodological 139:364–387. Choi Y, Schonfeld P (2017) Optimization of multipackage drone deliveries considering battery capacity. Transportation Research Board 96th Annual Meeting Transportation Research Board (Paper No. 17-0579) . Troudi A, Addouche S Sand Dellagi, Mhamedi A (2018) Sizing of the drone delivery fleet considering energy autonomy. Sustainability 10(9). Ulmer M, Goodson J, Mattfeld D, B W Thomas B (2017) Dynamic vehicle routing: literature review and modeling framework. Technical report, Technical University Braunschweig, Braunschweig. Ulmer MW, Thomas BW (2018) Same-day delivery with heterogeneous fleets of drones and vehicles. Networks 72(4):475–505.

ABSTRACT. We investigate a Rural Parcel Delivery by Drone Problem which arises, for instance, in low-density routes for the United States Postal Service, which involves a set of sparse customers and a road network comprising high- and low-speed vehicle routing arcs. Equipped with a companion drone, the vehicle is routed through the road network and may launch the drone to complete a delivery only from discrete locations along low-speed arcs that are close enough to the recipient. We develop a mixed-integer program that minimizes the time required for the vehicle and the drone to synchronously travel through the network and return to the depot, having completed all the deliveries exclusively by drone. This arc-based formulation is enhanced via a variety of preprocessing schemes and tighter big-M scalars that arise in constraints. Our computational study uses a dataset of randomly generated nodes that are geographically anchored in a rural setting in the USA, and demonstrates the computational benefit of the proposed preprocessing schemes.

ABSTRACT. As big metropolitan areas grow through suburbs, offering public transit with good service levels becomes economically expensive. Thus, semi-flexible transportation services are a good alternative to serve people that live in large low-demand areas. However, implementing semi-flexible transportation systems is a challenging task. Operators must set parameters that guarantee a good service level for commuters while striving to keep utilizations high and costs down. We developed a Markovian continuous approximation model to assess the performance of a flex-route service for different parameters such as schedule time, the width of deviation area, and the distance between stops. Thus, operators can determine the parameters by ensuring a target level of service.

ABSTRACT. Public transit is an essential infrastructure enabling access to employment, healthcare, education, and recreational facilities. While accessibility to transit is important in general, some sections of the population depend critically on transit. However, existing public transit is often not designed equitably, and often, equity is only considered as an additional objective post hoc, which hampers systemic changes. We present a formulation for transit network design that considers different notions of equity and welfare explicitly. We study the interaction between network design and various concepts of equity and present trade-offs and results based on real-world data from a large metropolitan area in the United States of America.

ABSTRACT. Paratransit services are indispensable for vulnerable road users, especially for the elderly and the disabled who lack other available mobility options or face lower accessibility to public transit systems. There are some recurrent disturbances that would be simpler to predict and, it is reasonable suspicion that there exists a significant relationship between the spatiotemporal characteristics of a location and the amount of potential delay. Therefore, this study proposes the incorporation of dwell time uncertainty in paratransit operation systems. It will use temporal multimodal multivariate learning (TMML) and the contextual bandit (CB) to estimate the impact of features on loading time.

ABSTRACT. We investigate the trade-offs between optimizing traditional costs versus adherence to standard practice. The standard practice is identified by historic solutions for related optimization problems. These historic solutions contain certain features that are attractive to the decision-maker, but their relative importance is unknown to us. Using outlier scoring techniques, we are able to generate new solutions that possess similar levels of attractive features as the historic solutions without explicitly modeling the importance of the individual features, thus adhering to the standard practice. We apply this procedure to a variant of the vehicle routing problem, and show how well features are identified using outlier scores and how the historic solution quality affects this process and the trade-offs. Furthermore, we compare two different well-known outlier scoring techniques: local outlier factor and isolation forests.

ABSTRACT. Home delivery services require the attendance of the customer during delivery. Hence, retailers and customers mutually agree on a delivery time window in the booking process. However, when a customer requests a time window, it is not clear how much accepting the ongoing request significantly reduces the availability of time windows for future customers. This paper explores using historical order data to manage scarce delivery capacities efficiently. We propose a sampling-based customer acceptance approach that is fed with different combinations of this data to assess the impact of the current request on route efficiency and the ability to accept future requests. We propose a data-science process to investigate the best use of historical order data in terms of recency and amount of sampling data. We identify features that help improve the acceptance decision and the retailer's revenue. We demonstrate our approach with large amounts of real historical order data from two cities served by an online grocery in Germany.

ABSTRACT. We study the vehicle routing problem with time windows (VRPTW) and stochastic travel times, in which related exogenous features are revealed to the decision-maker before routing decisions are made. Despite the extensive literature on stochastic VRPs, the presence of exogenous features has so far been ignored in this context. We address this research gap by introducing the feature-based VRPTW, which minimizes the total transportation cost and expected late arrival penalties conditioned on the observed features. Since the joint distribution of travel times and features is unknown, we present data-driven surrogate models that use historical data to provide an approximate solution to the problem. In particular, data-driven deterministic models formulate the surrogate problem in which travel times are fixed to some estimated values given, e.g., by a predictive model (predict-then-optimize paradigm). In contrast, data-driven stochastic models capture travel time variability by considering a set of travel time scenarios and formulating the corresponding sample average approximation (SAA) problem. In this setting, the decision-maker can take the observed features into account either by associating a feature-dependent weight function to each sample or by directly constructing feature-based travel time scenarios. We develop a specialized branch-price-and-cut method for solving the data-driven surrogate models and compare their out-of-sample cost performance in computational experiments. We achieve promising results by combining SAA with the generation of feature-based scenarios for travel times.

ABSTRACT. Courier services have a long tradition in city logistics. For short-trips, bicycle courier riders have some advantages compared to the classical car or van courier riders. In the last few years, there has been a change towards employee satisfaction to avoid they switch operators in a very competitive market. To achieve a higher satisfaction of the courier riders, one can include the individual preferences of the riders into the planning process. One important preference relates to the individual sense of safety with regard to the road network.

To this end, we propose a pickup and delivery model for this purpose. We build our model on a multigraph that represents different paths with respect to the safety preferences. The objective is to minimize a metric related to riders’ dissatisfaction incurred if they take the cost-efficient path instead of the preferred one while serving all customers.

We conducted some preliminary experiments indicating the relevance of the model. We defined two groups of riders, one with income preferences and one with safety preferences. As first results, we could identify types of instances where safety-oriented riders are forced to drive on some efficient paths on their tour. Second, we could show that different cities yield in different path selections. Third, we could show that the preference-oriented objective lead so different solutions than an efficiency-oriented objective.

ABSTRACT. In this work we study and introduce the Commodity Constrained Split Delivery Vehicle Routing Problem with Temperature Requirements (C-SDVRP-T), an extension of the Commodity Constrained Split Delivery Vehicle Routing Problem (C-SDVRP) in which each commodity must be transported under certain temperature regimes. As in the C-SDVRP, the C-SDVRP-T consists in defining a distribution plan to serve a set of customers, each requesting a quantity of different commodities. Each customer can be visited multiple times if each visit delivers different sets of commodities. Additionally, however, due to the temperature requirements it may be not possible to transport some set of commodities using the same truck. In fact, a set of commodities is feasible only if a target temperature that satisfies the temperature requirements of all the commodities in the set exists. This problem arises in temperature-controlled transport, where logistics providers use cooling/heating units to ensure the desired temperature for the cargo (target temperature), that must set in accordance with the requirements of the consolidated products. With the C-SDVRP-T, we integrate decisions on routing, target temperature, and cargo consolidation to minimize costs due to routing and refrigeration. We propose formulations and exact algorithms to solve the problem and demonstrate the benefits stemming from integrating temperature and routing decisions in terms of total costs.

ABSTRACT. Parking is a necessary component of last-mile delivery practices. Where to park the vehicle is a decision made by the delivery driver and this work brings insight into how to strategically make this decision. The Stochastic Last-Mile Parking Problem (SLMPP) is the problem of choosing a parking spot to deliver a package when driving around a rectangular block. We model the SLMPP as a Markov Decision Process. When the delivery driver finds an available parking spot, a solution to the SLMPP answers the following question: should the driver park or drive on? We characterize the structure of the optimal policy to the SLMPP dependent on the probability that each parking spot is available. Analytical results lead us to a polynomial-time algorithm that identifies the parking spots where the delivery driver should drive on, fully characterizing the optimal policy for the SLMPP. We extend the results to provide a framework and insight regarding the use of real-time reservation systems in last-mile delivery.

ABSTRACT. E-commerce retailers face the challenge of acting cost-efficient and becoming more sustainable at the same time, especially on the last mile, as the success of online retailers is strongly dependent on efficient delivery to the customer. Retailers therefore offer a range of delivery options that differ in terms of speed. While the trend is moving in the direction of same-day and instant delivery, a new concept already adopted by Amazon is to offer a slow delivery option, too. Faster delivery modes increase total costs and emissions by leaving less time for efficient planning and limiting consolidation possibilities on the last mile. Slowing down the delivery process offers the opportunity to increase shipment consolidation and thus save costs and take greater care of environmental demands simultaneously. The so-called "Some-Day Delivery" option significantly increases flexibility in tour planning. We formulate the stochastic-dynamic some-day delivery problem (SDDP) that considers delivery deadlines as well as routing and capacity constraints in a multi-period planning environment. Our numerical study shows that forecasting future customer orders and their associated delivery options is critical to finding feasible routes, balancing capacity, realizing consolidation opportunities, and thus cost savings.

ABSTRACT. Last-mile delivery with autonomous robots launched from dedicated delivery trucks is a promising approach to reduce logistics costs and inner-city traffic. Current literature for this innovative concept bases upon the use of a single truck to pick up multiple robots from robot depots and release them for delivery. This limits the practical use for industry applications in bigger cities. The demand for home deliveries is steadily increasing and with that the requirements for potential delivery by robots. The truck-and-robot concept therefore needs to be refined to meet these requirements by a fleet of delivery trucks.

We generalize the truck-and-robot delivery with robot depots for the simultaneous routing of multiple trucks. This means that a fleet of trucks is available and customer orders and robot deliveries must be assigned to delivery tours. We formulate this problem as multi-vehicle truck-and-robot routing problem. This extension includes the routing of multiple trucks and the corresponding clustering decisions, while choosing the optimal drop-off points for robots and their delivery. We develop a tailored heuristic solution approach based on a novel neighborhood search, the Set Improvement Neighborhood Search (SINS). We show that transportation costs can be reduced by up to 24% using our integrated approach of multi-vehicle routing and robot scheduling compared to a sequential cluster-first-route-second approach. Complementary experiments show a 62% savings potential compared to conventional truck delivery. We derive structural insights into the novel delivery system by analyzing the impact of changing customer distributions, delivery time windows, and truck or robot availability.

ABSTRACT. Restaurant meal delivery has been rapidly growing in the last years. The main challenges in operating it are the temporally and spatially dispersed demand from different customers all over town as well as the customers expectation of timely and fresh delivery. To overcome these challenges new business concepts emerge, called "Cloud kitchens", "Ghost kitchens", or "Dark kitchens". These concepts propose food preparation of several restaurants in a central complex in the city, thus, exploiting pooling benefits. In this research, we propose operational strategies for the effective operations of ghost kitchens. We model the problem as a sequential decision process. For the complex, combinatorial decision space, we propose a large neighborhood search that is based on properties that we developed for the optimal solution. Within the large neighborhood search, decisions are evaluated via a value-function-approximation, enabling anticipatory and real-time decisions. Last, we conduct numerical experiments to demonstrate the performance of our heuristic and to derive managerial insights.

ABSTRACT. Rapid and partially uncontrolled urbanization has led to soaring congestion in road networks, leading to discomfort for citizens, as well as to economic and environmental harm. With recent technological advances, Autonomous Mobility-on-Demand (AMoD) systems have emerged as a novel paradigm to complement traditional personal and public urban transport modes. In AMoD systems, a central operator controls a fleet of self-driving vehicles picking up users and transporting them to their intended destination. In this setting, serving each request as early as possible minimizes the user's waiting time but may prolong its driving time due to local congestion, which may arise during peak times on some road segments. Here, it can be beneficial to delay the departure of a ride - as long as the user's desired arrival time window is met - to reduce both the system's congestion and the user's driving time.We refer to the underlying decision problem as the staggered routing problem, in which an AMoD operator minimizes road blockage by delaying trip departures within the maximum time shift that a customer accepts. We formalize the problem as a mixed integer linear program (MILP) on a road network subject to congestion and propose a hybrid approach, combining local search techniques with our MILP. Our results on real-world instances show that delaying departures can significantly decrease congestion and travel times while ensuring punctual arrival for users.

ABSTRACT. Motivated by a supply network of medication for hospitals, we consider a multi-product two-echelon inventory routing problem with stochastic demand at both levels for a given and repeated planning horizon. Contrary to classical stochastic inventory routing problems, we are not interested in inventory decisions for each period of the planning horizon. Instead, we solve the inventory routing problem to determine a repetitive tour schedule and inventory control policies at both echelons. Additionally, just-in-time resupply is possible in case of stock-out. The problem is formulated as a two-stage stochastic program with resupply as recourse decision and solved using an efficient adaptive large neighborhood search. The numerical results demonstrate that the adaptive large neighborhood search outperforms CPLEX in both solution quality and run time. In a real-life case study, we show that the usage of just-in-time deliveries via drones reduces the costs by 15% at the central clinic and by 43% at small clinics.

ABSTRACT. The integration of warehousing and distribution operations allows a company to become "constraint-aware" in both inventory management and transportation management, which helps reduce the total operational cost and improve the customer service. In this paper, we study how to plan the daily delivery routes in such an integrated warehousing and delivery logistics system. We consider a manufacturer that sells multiple products to its customers distributed nationwide. The products are stored in a cluster of warehouses with various assortments and inventory levels. On a daily base, the manufacturer receives customer orders and decides a delivery plan to fulfill these orders, considering the product inventories and outbound shipment capacities of the warehouses. We formulate this problem as a binary integer linear program and develop a branch-price-and-cut algorithm, which consists of an efficient label-setting pricing algorithm and a customized branching scheme. We perform a comprehensive numerical study using test instances based on the (masked) real data from a manufacturer in China. The results show the efficiency and the effectiveness of the branch-price-and-cut algorithm. We also study and obtain practical implications on the impact of product inventories and outbound shipment capacities at the warehouses.

ABSTRACT. In real-time fleet management, input is unknown and revealed incrementally during the design or execution of the vehicle plans (routes). Consequently, the plans are defined in an ongoing fashion. Many important problems must be solved in real-time. Among them, there is the inventory routing problem (IRP), i.e., the delivery problem arising in situations where customers transfer the responsibility for inventory replenishment to the vendor. Then, the vendor must decide when to visit each customer over a specified time horizon, how much to deliver and how to sequence customers in one or more routes. Here we deal with a multi-vehicle IRP in which a fleet of vehicles has to serve real-time (or online) requests, i.e., demands which are revealed over time and are unpredictable accurately in advance. We refer to this variant as the Online Inventory Routing Problem (O-IRP).

For the O-IRP, we propose a class of online algorithms and present a competitive analysis to evaluate its performance from a theoretical perspective. Our approach is based on the solution of a mathematical programming model through a tailored branch-and-cut method in which several families of valid inequalities are separated and dynamically introduced in the model. The results obtained in the preliminary computational experiments encourage the use of the online algorithms defined in our study for uncertain settings. 

ABSTRACT. In this paper we address the Multicommodity Capacitated Fixed-charge Network Design problem with uncertain demands, which we formulate as a two-stage stochastic program. We rely on the progressive hedging (PH) algorithm of Rockafellar and Wets where the subproblems are defined using scenario groups. To solve the problem, we propose an efficient matheuristic approach which we refer to as the integrated learning and progressive hedging (ILPH). The proposed method takes advantage of a specialized learning-based matheuristic that is able to quickly produce high-quality solutions to multi-scenario subproblems. Furthermore, we propose a novel reference point definition, at each aggregation step of the PH algorithm, which leverages subproblem information regarding promising design variables. Extensive computational experiments illustrate that the proposed approach should be the method of choice when high-quality solutions to large instances of stochastic network problems need to be found quickly.

ABSTRACT. In recent years, the importance of decision support for the planning of multimodal itineraries has increased. Integrated mobility platforms promise travelers to create door-to-door itineraries considering their individual preferences based on the comprehensive breadth and quantity of mobility services such as trains, busses, and ridesharing services. Travelers expect a diverse set of combined mobility services according to several individual preferences. Although efficient approaches exist to find multimodal shortest paths, the full set of Pareto-optimal travel itineraries cannot be efficiently determined when considering multiple traveler preferences in a large multimodal network.

In this work, we propose a smart multi-criteria decision support system for efficient approximation of the Pareto front of multimodal travel itineraries by learning and predicting Pareto fronts. The framework is evaluated both from a traveler as well as from a technical perspective in detail using a large amount of real-world data of mobility services. For this purpose, we analyze long-distance travel between major cities in Germany considering up to five traveler preferences simultaneously.

ABSTRACT. In this paper, we address the location of locker boxes in the last-mile delivery context under uncertainty in demand and capacity. The problem is modeled as an extension of the capacitated facility location problem, in which a fixed number of facilities has to be opened, choosing among a set of potential locations. Facilities are characterized by a homogeneous capacity, but a capacity reduction may occur with a given probability. The uncertainty in demand and capacity is incorporated through a set of discrete scenarios. Each customer can be assigned only to compatible facilities, i.e., to facilities located within a given radius from the individual location. The goal is to first maximize the total number of customers assigned to locker boxes, while, in case of a tie on this primary objective, a secondary objective intervenes aiming at minimizing the average distance covered by customers to reach their assigned locker box. A stochastic mathematical model as well as three matheuristics are presented. We provide an extensive computational study in order to analyze the impact of different parameters on the complexity of the problem. The importance of considering uncertainty in input data is discussed through the usage of general stochastic indicators from the literature as well as of problem specific indicators. A real-world case related to the City of Turin in Italy is analyzed in detail. The benefit achievable by optimizing locker box locations is discussed and a comparison with the current configuration is provided.

ABSTRACT. Drivers traveling on the road usually choose the route which will reduce their own travel time without giving a thought about how this decision will affect other users in the traffic network. Their behaviours leads to problem of oscillating congestion on the roads in the event of traffic disruption. This paper addresses this issue by adopting a competing optimal approach for informed and uninformed drivers. Informed drivers are proposed with alternate routes that reduce the system cost while uninformed drivers continue their journey on originally proposed routes. This strategy of dispersing traffic can reduce congestion significantly. The framework is implemented using Transmodeler, a traffic simulation by experimenting with varying percentage of informed drivers in the network.

ABSTRACT. We propose a method for maximum likelihood estimation of route choice model parameters and arc travel time using data of different levels of granularity. Hitherto, these two tasks have been tackled separately hence ignoring their interdependence. We illustrate that this can lead to biased results and we propose an approach for simultaneous estimation. Results on simulated data show that our method, contrary to existing methods, is able to recover the ground truth parameter estimates. Furthermore, our method improves travel time estimates on the New York yellow cab dataset.

ABSTRACT. This paper proposes a fair and efficient demand management scheme, named CARMA, to address the morning commute congestion with heterogeneous travelers. We define a bottleneck model with two lanes: a fast lane operated at or below capacity and a slow lane subject to congestion. Commuters bid for access to the fast lane with karma, a non-tradable mobility credit. The bidding process repeats on a daily basis and at the end of each day, the karma collected from the bidding is redistributed to commuters. To capture the daily travel urgency of commuters, we generalize the notion of value of time (VOT) by allowing it to vary dynamically over time. We show the collective behaviors of a population of commuters under CARMA can be characterized by a dynamic population game and prove the existence of equilibrium. Further, $\karma$ is demonstrated, both analytically and numerically, to achieve a Pareto improvement compared to an optimal tolling scheme on the fast lane. With a well-designed karma redistribution scheme, it can even reduce the congestion of the slow lane.

ABSTRACT. Collaboration in humanitarian supply chain operations can lead to synergy, cost savings, and ultimately better outcomes. An important challenge is to identify the combination of collaborative partners that optimizes the benefit to society, termed the optimal coalition structure. This study applies cooperative game theory to model and solve the coalition structure problem among humanitarian supply chain entities to minimize total cost to society. Motivated by humanitarian supply chain characteristics and in contrast to most existing literature, this paper investigates a non-subadditive cost function where the collaborative benefit does not necessarily increase with coalition size. We propose a heuristic to solve the resulting problem and explore insights about the coalitions that are formed via a computational study

ABSTRACT. We establish a theoretical framework that links time-limited search problems with the prize-collection problems. Through this framework, we are able to efficiently solve such search problems using algorithms that are designed for the suitably-defined prize-collection problems. The base search problem includes an immobile entity/target that can be found at each node of a directed graph with a given a priori probability. The searcher’s objective is to travel a path with a particular origin and destination such that the probability of finding the entity is maximized. The searcher needs to reach the destination before the search time exceeds a predetermined time budget. As the searcher moves through the network, (s)he learns more about his/her surroundings, hence the a priori probabilities need to be updated. This iterative procedure helps the searcher choose his/her next moves using real-time data. Other variants are also built up on the base search problem, including searching for two immobile entities with (in)dependent Probability Density Functions (PDF)s and searching for an unknown number of entities. Computational results are presented at the end.

ABSTRACT. Free-floating micro-mobility systems have been widely adopted across the globe as a sustainable mode of urban transportation. To efficiently plan and operate such systems, it is crucial to understand underlying rider demand —- where the riders come from and the rates of arrivals over some given space. This is not straightforward as most systems only record trip data which is a biased representation of the underlying demand. In this paper, we develop a locational demand model to estimate rider demand. We establish conditions of identifiability and consistency of the parameters in our model. We also develop efficient and scalable computation procedures for the estimation problem. To demonstrate the efficacy of our model and estimation procedures, we test our model using real data from the dockless bike-sharing system in the Seattle area.

ABSTRACT. In this work, we propose an approach for designing a middle-mile consolidation network that aims to maximize the profit of large e-commerce retailers. We embed lead-time dependent sales volumes predictions into a new mixed-integer program (MIP) that determines shipment lead times and consolidation plans to maximize sales revenue net logistics cost. We propose a solution approach that uses an adaptive IP-based local search and dynamic lead time selection to find excellent consolidation plans for large, practically-sized instances. Preliminary results are illustrated using data from a U.S.-based e-commerce partner.

ABSTRACT. The trucking industry majorly relies on long haul to maximize truck utilization and consolidation opportunities. This generates long delivery trips for truck drivers, which recently led the industry to face truck driver shortages and retention issues. Relay-based transportation serves as a pragmatic solution where a truck driver can actively advance a load for half of their daily driving limit and can return home daily while the shipments travel towards their final destinations. In this work, we provide an optimization-based methodology to design a relay-based transportation network by strategically locating relay hubs. We formulate the problem as a two-stage stochastic program where we position and size the hubs in the first stage. In the second stage, upon realization of the demand uncertainty, we decide the frequency of trucks on the transportation links for transporting commodities through consolidation plan considerations and potential back-haul opportunities. Due to the integral nature of the second stage decision variables and problem size, the program becomes difficult to solve exactly via off-the-shelf solvers. We leverage the block-angular structure of the problem and employ a scalable Benders-decomposition-based heuristic to solve it. We depict the applicability of our solution approach through designing large-scale relay-hub network for a major car manufacturing company to be used for car deliveries in the South-East region of the USA. We show the importance of uncertainty consideration through evaluating the performance of the designed network against that obtained in a deterministic setting in various demand scenario realizations.

ABSTRACT. We propose a new approach to formulating the Scheduled Service Network Design Problem (SSNDP) that involves modeling with enumerated consolidations of shipments routed on the physical network. This is in contrast to the classical approach of capturing the synchronization of vehicles and shipments needed for consolidation with a time-expanded network. The proposed formulation has both a stronger linear relaxation and is less symmetric. We present multiple speed-up techniques and with an extensive computational study illustrate that the consolidation-based formulation is much easier to solve with an off-the-shelf solver than the classical formulation based on a time-expanded network.

To avoid instances involving large numbers of consolidations we propose a hybrid formulation that combines ideas from the consolidation and time-expanded network-based approaches to formulating the SSNDP. We show that instances of the hybrid formulation are much easier to solve than both instances of the pure consolidation-based formulation and those based on a time-expanded network formulation. Finally, we discuss how formulating with consolidations facilitates modeling issues that have not yet been addressed in the literature, such as bin-packing considerations when computing vehicle capacity needs. In addition, the proposed modeling technique for bin-packing considerations in a consolidation-based formulation yields instances that are easier to solve than those wherein capacity is modeled in an aggregate sense.

ABSTRACT. Highly efficient routing and scheduling plans for a heterogeneous workforce are challenging to develop for many firms offering services to customers in the home. In this paper, we focus on those firms that provide technical or maintenance related assistance. We present a model that schedules and routes heterogeneously skilled technicians serving a set of customers with demand for a variety of tasks revealed on a daily basis over a multi-period planning horizon, with the goal of minimizing the cost of serving all requests. These costs include the fixed cost associated with each technician working, the routing costs associated with technician travel, the service costs composed of preparation and task completion, and penalty costs associated with the delay in fulfilling a customer's request. We present this dynamic problem as a Markov decision process and introduce two heuristic algorithms that take advantage of problem characteristics to provide solutions efficiently. These heuristics, which simplify the model by reducing the goal function and approximating routing cost, are shown to be effective and efficient when solving real world sized problems. We use one heuristic to provide insight into managerial decisions associated with managing a team of technicians, showing that the benefit of cross-training technicians has limitations and that it is likely more efficient to have technicians with focused areas of expertise.

ABSTRACT. In ride-sharing systems, platform providers aim to distribute the drivers in the city to meet current and potential future demand and to avoid service cancellations. Ensuring such distribution is particularly challenging in the case of a crowdsourced fleet, as drivers are not centrally controlled but are free to decide where to reposition when idle. Thus, providers look for alternative ways to ensure a vehicle distribution that benefits users, drivers, and the provider. We propose an intuitive mean to improve idle ride-sharing vehicles' repositioning: repositioning heatmaps. These heatmaps highlight driver-specific earning opportunities approximated based on the expected future demand, current and expected future fleet distribution, and the location of the specific driver. Based on the heatmaps, drivers make decentralized yet better-informed repositioning decisions. As our heatmap policy changes the driver distribution in the future, we propose an adaptive learning algorithm for designing our heatmaps in large-scale ride-sharing systems. We simulate the system and generate heatmaps based on the previously learned policy in every iteration. We then update the policy based on the simulation's outcome and use it in the next iteration. We test our heatmap design in a comprehensive case study on New York ride-sharing data. We show that carefully designed heatmaps reduce service cancellations therefore revenue loss for platform and drivers significantly while leading to a better service level for the users and to a fairer treatment of drivers.

ABSTRACT. Given a set of transport requests to a transit station and a set of homogeneous vehicles, both geographically dispersed in a business area, the First-Mile Ride-Sharing Problem (FMRSP) consists of finding least cost vehicle routes to transport passengers to the station by shared rides as well as preventive movements of idle vehicles (i.e., rebalancing) in order to anticipate future demand. In this talk we present a new MILP formulation for the problem as well as an ALNS metaheuristic to solve large scale instances. The online FMRSP is solved with a rolling-horizon process to investigate the effect of rebalancing movements. Furthermore, we compare the ALNS algorithm against GUROBI solver. Preliminary results show that the solver cannot solve moderately sized instances to optimality within the time limit, while the ALNS algorithm can address much larger instances.

ABSTRACT. The Production Routing Problem (PRP) is a core problem in the integrated planning of supply chains. It involves the joint and simultaneous optimization of production (including set ups), inventory, distribution, and routing decisions. While many variants of the general PRP can be found in the literature, most of them consider only deterministic data. This is a significant concern, as uncertainty is a major issue in supply-chain management. In this paper, we consider a PRP over a finite horizon, with a single capacitated production facility, multiple products, a fleet of homogeneous vehicles, and uncertainty in the availability of vehicles. This is a problem setting not considered by previous studies, but commonly found in industrial environments.

We propose a chance-constrained model to tackle this problem. It involves using Monte Carlo sampling to define scenarios on the availability of vehicles in each period of the planning horizons. We then derive constraints that count the fraction of scenarios and periods for which the required number of vehicles is available. These constraints are added to an efficient model for the deterministic PRP.

The proposed model is solved using Partial Benders decomposition. Detailed computational results will be presented at the conference.

ABSTRACT. When there is limited intermediate storage capacity between the production and transportation phases of a supply chain, an integrated solution method is required to obtain a good synchronization. This is crucial to avoid blocking in the production process, which would cause inefficiencies. We introduce a generalizable model for such problems, covering the most important interaction between the different phases, while still easy to extend with additional constraints. We also propose a solution framework based on Hybrid Genetic Search in order to find feasible and good solutions. Finally, we validate the solutions with a case study relating the compound feed industry.

ABSTRACT. The Production Routing Problem (PRP) is a generalization of the Inventory Routing Problem and includes the production and distribution of a single product from a production plant to multiple customers using capacitated vehicles in a discrete and finite-time horizon. The ability to solve the PRP contributes to the realization of the potential savings in production, inventory and transportation costs brought about by vendor managed inventory replenishment considering production and routing decisions. In this work a new heuristic is proposed using a relaxation of the PRP with predetermined routes. Therefore, a new clustering method is provided considering inventory and demand ratio. To enhance the obtained PRP solution, determined routes can be improved by local search, considering vehicle capacity and vehicle load information. The heuristic is tested on standard instances from the literature. First computational results show that the heuristic is competitive with approaches from the literature and superior to some approaches in terms of computation time and solution quality.

ABSTRACT. Attended Home Deliveries (AHDs) are characterized by dynamic customer acceptance and narrow customer-specific delivery time windows. Both impede efficient routing and thus make AHDs very costly. In this paper, we explore how established horizontal collaborative transportation planning methods can be adapted to render AHDs more efficient. The general idea is to enable request reallocation between multiple collaborating carriers after the order capture phase. An auction-based framework is used that allows participating carriers to buy and sell delivery requests without full disclosure of business information. The framework is extended for AHD specifics such as the dynamic arrival of customer requests and information about delivery time windows. Using realistic instances based on the city of Vienna, collaboration savings are quantified by solving the underlying routing and auction problems. The experiments show that narrow time windows can lower the savings obtainable by the combinatorial auction by up to 15%. Therefore, we suggest enhancing the decision processes of request selection and request bundling using information about delivery time windows. Our findings demonstrate that adapting methods of request selection and bundle generation to environments with narrow time windows can increase collaboration savings by up to 25% and 35%, respectively in comparison to methods that work well only when no time windows are imposed.

ABSTRACT. We consider the problem setting of a less-than-truckload carrier serving stochastic customer requests. Each request must be answered dynamically by accepting or rejecting it immediately. On the next day, the accepted requests are served in routes using a set of vehicles with limited load capacity and route duration. After the request acceptance phase and before the requests must be served, multiple carriers participate in a combinatorial auction to exchange a subset of requests. After carriers place bids on bundles of requests, an auctioneer allocates the bundles to carriers in a cost-minimizing way and distributes the auction profits. This type of horizontal collaboration provides cost savings to carriers and contributes to reducing negative impacts of transportation such as emissions or traffic. Each carrier’s optimization problem of maximizing profit can be modeled as a Markov decision process that comprises the sequential decisions in all phases, i.e., request acceptance, request selection for the auction, bidding, and routing. Heuristic approaches are proposed to generate preliminary route plans and for considering the options provided by the auction already when making request acceptance decisions. We specifically consider overbooking policies for accepting more requests than can be served before the auction takes place and the strategic rejection of requests in anticipation of more profitable upcoming requests. Numerical experiments show that carriers’ request acceptance decisions impact their individual profits and the overall collaboration savings. The largest benefits can be achieved with an overbooking policy that is applied by all carriers and considers the locations of both the request and the carriers’ depots.

ABSTRACT. The Collaborative Vehicle Routing Problem (CVRP) accounts for the most challenging part of the collaborative last-mile logistics, which is believed to significantly propel the development of sustainable and efficient freight distribution systems. Centralized CVRP (CCVRP) is a class of CVRP which assumes a central planer with complete information and generally produces higher performance than other counterparts. While most studies in CCVRP focus on constructing new VRP variants for various scenarios and proposing bespoke algorithms, few of these algorithms are transferable for solving other formulations.

In this work, we propose a novel distributed algorithm for CCVRP based on game-theoretic control. It is independent of underlying routing formulations and theoretically converges to equilibria of a welfare sharing game. Its performance is bounded by evaluating corresponding equilibria. The best possible performance is always as efficient as central optimisation while the worst performance is instance-specific and can be estimated by solving a bi-level optimisation. Simulation results show that our algorithm guarantees at least 46% of centrally optimised performance and could improve the system performance by 36.24% when compared with non-collaborative operations.

ABSTRACT. We propose a spatial covering formulation for mobile facilities operating over a multi-period time horizon. The objective is to route a fleet of mobile facilities through a sequence of parking locations according to a predefined temporal schedule to maximize the customer reward collected from the regions of the respective parking locations. We consider capacitated mobile facilities and stochastic demand arising from customer discretion on when and where to visit mobile facilities. We present computational results for sampling-based variable neighborhood search benchmarked by upper and lower bounds resulting from a linear integer program treating demand as a deterministic assignable quantity.

ABSTRACT. In typical applications of facility location problems, the location of demand is assumed to be an input to the problem. The demand may be fixed or dynamic, but ultimately outside the optimizer’s control. In contrast, there are settings, especially in humanitarian contexts, in which the optimizer decides where to locate a demand node. In this work, we introduce an optimization framework for joint facility and demand location. As examples of our general framework, we extend the well-known k-median and k-center problems into joint facility and demand location problems (JFDLP) and formulate them as integer programs. We propose a local search heuristic based on network flow. We apply our heuristic to a hurricane evacuation response case study. Our results demonstrate the challenging nature of these simultaneous optimization problems, especially when there are many potential locations. The local search heuristic is most promising when the number of potential locations is large, while the number of facility and demand nodes to be located is small.

ABSTRACT. We consider a setting in which a central planner allocates a finite set of resources to a finite set of agents with unit demand without monetary transfers. Agents may share a resource and bear a congestion cost, so that the utility that an agent derives from a resource is decreasing in the number of agents sharing that resource. We define a notion of a stable allocation in this setting, which we call a weak core allocation. We show that there is no nonmonetary mechanism that identifies a weak core allocation and that incentivizes truthful participation. However, we define a mechanism that produces the least possible incentives for untruthfulness. Our proposed mechanism is a type of ascending auction in which the auctioneer states the number of participants that will share each element rather than the price.

ABSTRACT. Advances in information-sharing technology have stimulated innovative ways to deal with the increasing demands in the domain of logistics and transportation. Among them, collaborative planning strategies, where individual stakeholders can provide service cooperatively based on resource (e.g., infrastructure and information) sharing, are widely accepted as a promising approach to numerous decision-making problems. Accounting for over 90% of global trade, the maritime shipping industry faces great opportunities as well as challenges related to collaboration. In this paper, we extend the work of Lyu et al. (2022) to study the Collaborative Berth Allocation Problem (CBAP) in which all terminals within one port serve the calling vessels cooperatively. First, we present a mathematical model to minimize the cost of discharging (or loading) operations for the terminal operators and the turnaround time for the calling vessels. Second, we develop a row-generation-based algorithm to calculate the core solution for distributing the joint cost. Third, we further develop the algorithm to verify and find the nucleolus solution to distribute the joint costs among collaborative terminal operators. The computational results show that the core solution obtained by the proposed row-generation algorithm can satisfy the coalition rationality requirements. Moreover, the designed mechanism derives nucleolus solutions such that each member realizes clear cost savings relative to the row-generation solutions, in all conducted experiments. In summary, the CBAP model and cost allocation methods (the core and the nucleolus) based on Cooperative Game Theory proposed in this work not only show the great potential of collaborative strategies but also provide maritime practitioners with strong decision-making support to implement collaboration in practice.

ABSTRACT. Methods to improve the performance of dynamically managed network-based systems often consist of the design of practical heuristics. In the past, the performance evaluation of such dynamic solution methods has received limited attention. Often these methods are compared against regret-based bounds or omniscient information-based bounds, such as in online optimization and machine learning literature (Van Hentenryck and Bent 2009, Flajolet and Jaillet 2017). We focus in this work on improving upon long-used regret bounds that are based on omniscient information about the future. Our work builds on Brown, Smith, and Sun (2010), who present an approach for information-relaxation bounds in dynamic programs. Their approach relaxes non-anticipativity constraints that restrict the information available to dynamic programs, and instead, penalize the additional information available to the anticipative decision-maker who knows (part of) the future. However, the computation of these penalized information-relaxation bounds (or penal- ized regret bounds) for large-scale systems has been discussed by many authors to be intractable (Kullman 2020, Kullman, Goodson, and Mendoza 2021, Maxwell et al. 2014). We present tractable methods to achieve bounds for time-space network-based problems and problems modeled as block-diagonal mixed-integer programs.

ABSTRACT. E-scooter sharing systems have emerged as an important and promising part of urban shared mobility services. However, the growing fleet in an e-scooter sharing system imposes great challenges in the rebalancing and recharging operations for the system operator. In this work, we consider a novel approach to handle this issue and propose a mathematical optimization model to solve the problem. Using a truck equipped with battery charging capability, the system operator jointly makes the routing, waiting, and handling decisions in an e-scooter network to meet the needs of its customers. We formulate the integrated decision problem as a two-stage mixed-integer linear program. We show that the second stage of the problem can be solved efficiently by solving a linear program. We propose an effective algorithm to solve the integrated decision problem based on Benders decomposition. We validate our framework with numerical experiments.

ABSTRACT. Ridesharing is an emerging mode of transport that allows passengers with similar itineraries to share a ride instead of each going individually. Such schemes reduce congestion on the roads and can lead to relatively large mileage reductions. In this paper, we study a strategic decision-making problem for the design of ridesharing networks. We consider an urban area where the decision-maker wants to promote shared transportation through the deployment of ridesharing connections. Given the trips of passengers in this urban area, the problem is to determine the origins and destinations of a fixed number of ridesharing connections to maximize the potential users of this system. Each origin-destination trip in this urban area is a candidate for using a ridesharing connection only if the start and end points of the trip are within a given walking distance (for example, within 500 meters) of the beginning and end nodes, respectively, of the ridesharing path. We assume that there is a limit (or budget) on the ridesharing connections to be deployed representing, for example, the available number of shuttles. We propose and compare different methodologies to address this problem. In particular, we develop an optimization model and additionally propose two clustering-based data-driven approaches. The contributions of this study are (i) development of an optimization model to address the ridesharing hub network design problem, (ii) development of a Benders decomposition algorithm together with several algorithmic enhancements to efficiently solve the optimization model, (iii) implementation of two clustering-based data-driven methodologies to address the problem, (iv) comparing the results obtained from the optimization and data-driven approaches under several performance indicators to derive insights.

ABSTRACT. Increasing fleet utilization is one of the main drivers for operational performance in car rental as well as in car sharing. This is why, most recently, car rental providers which traditionally only offered long-term rentals have begun to offer short-term (car sharing-like) rentals in addition – and vice versa. We study a shared mobility system provider who offers both long- and short-term rentals, in order to assess the benefits and drawbacks of combining car rental and car sharing. In such a combined system, the vehicle fleet becomes the common resource for which car rental and car sharing demand compete. While overall demand increases in a combined system, the assessment of this effect on important performance metrics like revenue, rentals, utilization, and service is not straightforward. For example, short-term rentals come along with a higher revenue per minute, but a single such rental may occupy a potentially scarce resource and may thus displace a long-term rental which could generate much higher absolute revenue. Considering that long- and short-term demand follow very different patterns complicates the assessment. To quantify benefits and drawbacks, we consider the combined system on an aggregate level that replicates a typical week. Throughout the entire work, we take a systematical approach that is based on two perspectives, meaning a car rental provider that additionally offers car sharing, and vice versa. This differentiation is important because car rental providers typically manage the incoming requests for future rentals through availability control while car sharing providers typically decide on prices that result in rather spontaneous rentals. Methodologically, we base our analyses on mathematical optimization. To this end, we propose two general models that reflect the particularities of the two perspectives and that allow to analyze different degrees to which a provider additionally offers the respective new mobility concept. The managerial insights gained are based on numerical studies that use data from real-life car rental and car sharing providers. With this work, we pioneer research on combined car rental and car sharing systems. By providing several managerial insights, for example by showing that transitioning towards a combined system is not equally attractive for car rental and car sharing providers, we support mobility providers in their strategic decision-making regarding their mobility portfolio.

ABSTRACT. We consider the problem of routing k service agents to service customers with known and unknown service request times at the beginning of an operational period. We propose a branch-and-price approach to generate routes to minimize the total expected waiting time of all considered customers. Our approach utilizes the full distribution of service request times and our results show that the value of our approach grows as the number of stochastic service request customers grows, with respect to point estimate and greedy alternatives.

ABSTRACT. We present the Stochastic Selective TSP with Generalized Latency, SSTSP-GL, a problem arising on the tactical level of Demand Adaptive Systems. The SSTSP-GL is an extension to the Symmetric TSP with Generalized Latency (TSP-GL), which is a variant of the Symmetric TSP, where the objective function is the sum of tour design and passenger routing cost. Our main contributions include the sampling-based formulation of the SSTSP-GL and decomposing the SSTSP-GL, which allows us to utilize a Branch-and-Price (B&P) framework. This decomposition enables us to reduce the subproblems of the B&P framework to TSP-GL problems which we can solve via Benders decomposition.

ABSTRACT. This study introduces the multi-attribute two-echelon location-routing problem with stochastic travel time (MA-2ELRPSTT). Prompted, in particular, by city-logistics applications, the system concerns the definition of two levels of vehicle routes to enable demand distribution from a set of platform facilities to the end customers, through an intermediate set of facilities named satellites. The problem setting includes time-dependent multicommodity demand, time windows, limited storage capacity at intermediate facilities, synchronization at these facilities of the fleets operating on different echelons and uncertain travel times. We formulate the problem as a two-stage stochastic programming formulation, with platforms and satellites location-allocation decisions concerning the first stage, while recourse decisions are made in the second stage to distribute customers with the observed travel times. The main objective of the resulting MA-2ELRPSTT is then to minimize the total cost of the system, composed of the design cost, which concerns the location and allocation decisions for both platform and satellite facilities, and the expected distribution costs (the recourse function) while satisfying the demand and the capacities of the system. A progressive hedging metaheuristic is proposed as the solution method for the proposed formulation. Two population structures are embedded in the proposed progressive hedging framework to broaden the options of the design decisions archived for each scenario subproblem and to derive key insights to improve the solution diversity. We also introduce and compare novel strategies to accelerate the search for the solution space for the stochastic problem. These acceleration strategies are incorporated into the solution framework, where extensive computational experiments demonstrate the efficiency and effectiveness of each strategy to produce high-quality solutions under a variety of problem characteristics and travel time uncertainty.

ABSTRACT. There are emerging transportation problems known as the Traveling Salesman Problem with Drone (TSPD) and the Flying Sidekick Traveling Salesman Problem (FSTSP) that involve the use of a drone in conjunction with a truck for package delivery. This study represents a hybrid genetic algorithm for solving TSPD and FSTSP by combining local search methods and dynamic programming. Similar algorithms exist in the literature. Our algorithm, however, considers more sophisticated chromosomes and simpler dynamic programming to enable broader exploration by the genetic algorithm and efficient exploitation through dynamic programming and local searches. In particular, our genetic algorithm generates the truck and the drone sequences separately and encodes them in a type-aware chromosome, wherein each customer is assigned to either the truck or the drone. We apply local searches to each chromosome, which is decoded by dynamic programming for fitness evaluation. Our dynamic programming algorithm, called JOIN, merges the two sequences by determining optimal launch and landing locations for the drone to construct a TSPD solution represented by the chromosome. We propose novel type-aware order crossover operations and effective local search methods. A strategy to escape from local optima is proposed. Our new algorithm is shown to outperform existing algorithms on benchmark instances in both quality and time.

ABSTRACT. Introduction Transport of goods is an essential factor for economic development in an urban area. With the rise of transportation problems for product deliveries in urban areas, the concept of city logistics is introduced. City logistics aims to optimally plan, manage, and control the vehicle movements within a logistical network in an urban area, considering integration and coordination among involved stakeholders (Neghabadi, Samuel, and Espinouse 2019). Since collaboration is a crucial element in city logistics (Crainic, Gendreau, and Jemai 2020, Lagorio, Pinto, and Golini 2016, Neghabadi, Samuel, and Espinouse 2019), innovative solutions for city logistics related to this element have been introduced over the years. Companies can, for example, collaborate to bundle freight flows in a two-or multi-echelon system using one or more intermediate consolidation points, such as urban consolidation centers (UCCs), city depots, micro hubs, etc.

Multi-echelon systems have been widely used in cities around the world. In most city centers, road space is limited and has to be shared with private and public passenger transport and parking facilities (Hemmelmayr, Cordeau, and Crainic 2012). Besides, heavy freight transportation in a city is a discomforting factor for citizens because it produces congestion, polluting emissions, and noise. As a result, city authorities usually want to reduce the number of large vehicles and only allow smaller vehicles in the city center. Although multi-echelon systems may help to achieve this, the additional costs of implementing a city hub (e.g., cost of the facility, additional handling) make it important to discuss the broader implications and potential cost reductions in other processes of the stakeholders involved.

Both in practice and academia, the main focus when implementing or studying multi-echelon systems is on the opportunity to consolidate transport flows, leading to more efficient and more environmentally friendly transportation activities. Another opportunity in such a system is to use the consolidation points as temporary storage facilities in a B2B setting, so that retailers can save costly storage space in the urban area. However, the study of inventory aspects in city logistics is relatively unexplored. Therefore, this work aims to study the opportunity of using UCCs as an intermediate storage point in an urban two-echelon distribution system. More specifically, our goal is to analyse to what extent the integration of inventory and routing decisions leads to additional operational benefits compared to a traditional setting in which the UCC is only used as a consolidation point.

The type of problem that integrates routing and inventory decisions is known as the Inventory Routing Problem (IRP). In the VRP, the main decision to make is the set of routes to travel in a single time period. In the IRP, three main decisions must be taken in a multi-period setting: when and how much to deliver to each customer and the routes to travel at each time period. Therefore, the IRP adds some complexity due to the integration of inventory and routing elements into a multi-period decision process, but it may lead to better overall decisions. While the IRP has been studied extensively, only a few studies consider inventory aspects along with the routing decisions in a city logistics context, with its specific characteristics. Examples of such characteristics include time windows, multiple vehicle trips per day, the use of heterogeneous vehicles, etc. In this work, we address this gap by modeling and solving an IRP in an urban context.

Problem Description Our problem setting can be described as follows. We consider an urban two-echelon distribution system in which the network consists of a number of suppliers (outside the urban area), a single UCC, and multiple urban retailers. Retailers face a daily demand from their customers for multiple products over a predefined multi-period planning horizon. Each retailer orders the required products from the different suppliers (a single supplier per product type). Suppliers deliver their products to the UCC, after which they are consolidated and distributed to the retailers from the UCC using a heterogeneous fleet (e.g., bikes and vans). Retailers have a limited storage capacity, face a holding cost when storing products over the periods, and impose strict time windows on deliveries. Finally, holding costs at the UCC are assumed to be lower than at the retailers' locations, and bikes can make multiple trips per period.

To address our research question, two scenarios are considered and compared: a traditional one in which inventory and routing decisions are taken sequentially and an integrated one in which both decisions are taken simultaneously. In the first scenario, each retailer defines its orders based on a replenishment method over the multi-period planning horizon. Then, the suppliers deliver their products to the city hub on the requested days, and the city hub handles the delivery process of the products from all suppliers to the retailers. This involves solving a VRP with time windows, heterogeneous fleet and multiple trips on each day of the planning period. In the second scenario, the city hub simultaneously defines how many products of each type will be delivered to the retailers and the delivery routes, while ensuring sufficient inventory at the retailers. Therefore, the inventory and routing decisions are optimized simultaneously by the city hub. This results in a multi-period IRP with multiple products, time windows, a heterogeneous fleet and multiple trips.

Solution method The inventory and routing decisions are made sequentially for the first scenario. In the inventory part, the retailers decide when and how many products to receive from the suppliers. To determine the delivery amount for each period, the retailers are assumed to use one of five different replenishment methods. For the first three replenishment methods, a periodic delivery method is used. In these methods, the delivery amount is the sum of the retailer’s demands for n periods, with n being either 1, 2, or 3. The fourth replenishment method is an Order Up to policy (OU), in which the inventory level is raised to its maximum capacity whenever a retailer needs to be replenished. The last replenishment method applies the principle of Economic Order Quantity (EOQ). After determining the order quantity using one of the replenishment methods, a list of retailers that need to be visited and their order quantity for each period is generated. Then, for the routing part, a Large Neighbourhood Search (LNS) meta-heuristic algorithm is used to solve the route optimization problem. The best insertion heuristic is used to obtain an initial solution to the problem and to rebuild destroyed solutions. We use three types of removal mechanisms as the destroy operator: random removal, trip removal, and worst removal. In each iteration of the algorithm, one of these is selected randomly.

In scenario 2, the inventory and routing parts are optimized simultaneously. In addition to the delivery routes, the city hub must also define how many products to deliver to the retailers to have a minimum total cost. To solve this problem, we propose a matheuristic algorithm, based on the one proposed in Bertazzi et al. (2019) and extended for the multi-trip aspect in our problem. The matheuristic method consists of two phases: a route generation phase and an optimization phase. In the route generation phase, a large set of promising delivery routes is built. To this end, we run our LNS algorithm on the daily routing problems that result from applying the different replenishment policies considered in scenario 1 and store routes found during the search. Next, we enlarge the route pool by recombining trips into new delivery routes. For the optimization phase, we present a mixed integer linear programming model to simultaneously select routes from the route pool for every period and determine the delivery quantities to the retailers for each of these selected routes. The model minimizes the total routing and inventory cost, and is solved using CPLEX.

Computational Results A numerical study is conducted to compare the two scenarios. Several problem characteristics are varied in this study, including the number of suppliers, the number of retailers, the holding cost, and the replenishment method applied by the retailers in scenario 1. Several values for each problem characteristic are considered, and each unique combination is tested. Artificial instances that correspond to each combination are generated and solved for both scenarios. With these computational experiments, we aim to see the impact of integrating inventory and routing decisions in a city logistics context. Preliminary results indicate that scenario 2 provides better solutions in terms of the total cost than scenario 1. Improvements of about up to 50% are found. In addition to the total cost, some performance measures related to the city perspective, such as the traveled distance, average vehicle loading degree, and the number of urban trips, are used for the evaluation process.

References Bertazzi L, Coelho LC, De Maio A, Lagana D, 2019 A matheuristic algorithm for the multi-depot inventory routing problem. Transportation Research Part E: Logistics and Transportation Review 122:524–544, URL http://dx.doi.org/10.1016/j.tre.2019.01.005. Crainic TG, Gendreau M, Jemai L, 2020 Planning hyperconnected, urban logistics systems. Transportation Research Procedia 47:35–42, URL http://dx.doi.org/10.1016/j.trpro.2020.03.070. Hemmelmayr VC, Cordeau JF, Crainic TG, 2012 An adaptive large neighborhood search heuristic for Two-Echelon Vehicle Routing Problems arising in city logistics. Computers & Operations Research 39(12):3215–3228, URL http://dx.doi.org/10.1016/j.cor.2012.04.007. Lagorio A, Pinto R, Golini R, 2016 Research in urban logistics: a systematic literature review. International Journal of Physical Distribution & Logistics Management 46(10):908–931, URL http://dx.doi.org/10.1108/IJPDLM-01-2016-0008. Neghabadi PD, Samuel KE, Espinouse ML, 2019 Systematic literature review on city logistics: overview, classification and analysis. International Journal of Production Research 57(3):865–887, URL http: //dx.doi.org/10.1080/00207543.2018.1489153.

ABSTRACT. Drone package deliveries are quickly taking off, but they carry unique integration and deployment considerations. There is a risk to customer privacy that arises as a result of remote identification laws, which require drones to broadcast position information while in operation. A third-party observer can use that information to reconstruct a drone's trajectory and potentially deduce which vendor a customer ordered from. Therefore, drone delivery service operators may be interested in how they can route their vehicles efficiently while considering customer privacy risk. In this work, we show how privacy risk may be approached as an optimization problem, then integrated within a vehicle routing problem formulation. Specifically, we propose a two-stage decomposition in order to be able to formalize the model. We then show how to integrate privacy risk considerations into the vehicle routing problem. Privacy requirements are considered from an operator's perspective as a constraint and from customers' perspective as an objective to be traded off with delivery time.

ABSTRACT. Scheduling of connected and autonomous vehicles (CAVs) at a reservation-based intersection is essentially an Markov decision process (MDP). Existing solution methods solve the MDP by re-formulating it as a mixed integer programming (MIP) model. However, it takes exponential growth time for a state-of-art solver to find the optimal solution from the MIP. This work reduces the time complexity of dynamic programming (DP) algorithm by exploiting a customized cut at each node in the decision tree. The customized cut is analytically derived based on predicting all possible future scheduling sequences. The predict-then-optimize analytical solution method reduces the time complexity to the polynomial growth time of the problem size. The numerical examples also analyze the computation time under stochastic arrival settings. From the numerical analyses, this work provides managerial insights into the scheduling policy and trajectory planning of CAVs at a reservation-based intersection.

ABSTRACT. Alternative fuel vehicles may pose challenges to evacuation planning due to their short driving range and sparse refueling infrastructure on transportation networks. Deployment and strategic siting of emergency refueling stations are needed to support the evacuation of alternative fuel vehicles to reach a shelter. This study proposes a location-routing problem with hop constraints that optimize the placement of emergency refueling stations of each alternative fuel type to support evacuation routing. We develop a Benders-inspired decomposition method with a transformed network to solve the location problem and a matheuristic branch-and-price method to design evacuation routes that minimize travel and refueling time and satisfy the hop constraints of each vehicle type. Our numerical experiments, focusing on the South Florida network, uncover the impacts of alternative fuel vehicle specs and vehicle heterogeneity on the deployment plan.

ABSTRACT. The dynamic dispatch waves (DDW) problem considers a vehicle routing variant where requests are not known beforehand but arrive dynamically. This means that apart from finding optimal routes, you should also decide between dispatching an order in the current epoch or postponing it to later. We study a variant of the DDW problem where each customer request has a time window during which the request must be served. The goal is to minimize the total distance traveled. We propose an efficient online policy that relies on simulation based on historical request data for the dispatch decisions. For solving static instances, we rely on an algorithm that we developed based on hybrid genetic search. We show that we can outperform generic baseline policies for the dynamic problem and analyse the gap towards a solved hindsight solution. This algorithm has also proven itself by being ranked third in the EURO meets NeurIPS 2022 vehicle routing competition.

ABSTRACT. We address a multi-period allocation-routing problem with a heterogeneous fleet for disaster response. We introduce a tour generation and adaptive neighborhood search algorithm to solve the problem efficiently. In our experiments, trucks perform bulk deliveries and drones as an alternative vehicle. We analyze various fleet configurations and supply scenarios in a case about the 2015 earth- quake in Nepal. Results show that small deliveries to various locations in multiple periods introduce higher transportation costs, but significantly lowers deprivation costs. Especially in situations with scarcity of supplies, deploying more expensive drones can provide significant improvements in terms of decreasing deprivation of disaster-affected people.

ABSTRACT. We study a Last Mile Delivery (LMD) problem that deals with fleet sizing decisions of a company. While existing studies primarily focus on the day-to-day operational aspect of the LMD systems, our aim is to explore the problem at a tactical level where the number of freighters to be hired by the company is fixed for a long period of time (e.g., 4 months). We mimic large real cities that are usually divided into regions and further divided into areas, and the packages first reach Local Distribution Centres (LDCs) located within each area, from where they need to be delivered to the end customers using green means like bikes or simply walking. This study is particularly aimed at complementing innovative LMD strategies, where the use of delivery trucks is limited. We intend to estimate the number of freighters to be hired by the company not only for the entire city but also for each region and area to serve the demand during different time periods of the day. One of the novel aspects of our study is that the freighters are allowed to serve different areas during different periods depending on the demand distribution. The unserved demand is assumed to be outsourced, and our objective is to balance the hiring and outsourcing costs over the planning horizon. We propose mixed integer programming techniques to study a stochastic version of the problem. We use an approximation algorithm to capture the operational requirements of the system and embed it into our model. We provide computational studies to support the viability of our studies.

ABSTRACT. We study a fleet composition problem with stochastic and bounded, periodic demand, which must be fulfilled via a combination of internal truckload (TL) capacity and external less-than-truckload (LTL) shipments. Internal capacity costs include a fixed ownership cost per truck and a fixed dispatch cost per truck trip, while LTL costs are incurred per unit shipped. We characterize the expected shipping cost per period as a function of internal fleet size for both homogeneous and heterogeneous fleets. For certain demand distributions, we explore the properties of the optimal fleet size, and the corresponding expected quantities shipped via TL and LTL, respectively.

ABSTRACT. Mass testing is an intervention strategy for pandemic control in the general population regardless of the presentation of symptoms. It involves, e.g., gargle test collection for PCR analysis. Countries that have applied mass testing consider it to be a viable strategy as it potentially identifies asymptomatic cases, which can then be isolated in the early stages of infection. By this, the risk of virus transmission can be considerably reduced. In the City of Vienna, such a mass testing porgram has been established in 2021. This testing program allows citizens to perform PCR gargle tests at home. Test kits can be collected, free of charge, from and returned to supermarkets, drugstores, gas stations etc. From there, they are collected by a logistics provider and delivered to a central laboratory. Test results are expected to be available within 24 hours after the test was picked up. Typically, pick ups are performed twice a day. For the matter of efficiency and also in order to offer a reliable service to regular customers, pick up times are required to be consistent over the whole planning horizon. In our study, we address this multi-period vehicle routing problem faced by the logistics providers, which have to pick up test kits from several hundred locations within narrow time windows and under the expectation of consistency of arrival times. Additional challenges stem from the fact that the laboratory expects a continuous arrival of vehicles with similar loads to avoid unbalanced workloads, which might cause bottlenecks and consequently delays in test result deliveries. Furthermore, it is possible to reduce the pick up times at the customer locations by increasing the number of drivers on each vehicle from one to two drivers. In order to solve the problem, we propose a solution approach based on the generation of template routes for each subperiod. These routes are adapted for each period and each subperiod using the real amount of PCR test kits to be picked up from the locations. We combine a constructive heuristic with two versions of an adaptive large neighborhood search metaheuristic. Furthermore, in order to improve the arrival time spread aspect of the problem, we solve a mathematical subproblem, where the arrival times of vehicles to the locations are determined. For our computational study we use data from the real world testing program in Vienna. We assess the performance of the proposed solution approach and gain several managerial insights. Furthermore, we are able to compare the obtained solutions to the routes performed by the logstics provider. Based on this, further insights on real world challenges can be derived.

ABSTRACT. The analysis of logistic challenges in the humanitarian sector is an active and vibrant field of research, and though a large variety of problems has been studied, they either consider a single period or aggregate decisions for multiple periods in a manner that diminishes this aspect. To account for this gap, we investigate a logistic problem that involves vehicle routing and resource allocation, based on a food aid operation (inspired by the Israeli food bank “Latet”). We show that decomposing the problem by periods leads to poor-quality solutions, and discuss alternative procedures that lead to improved solutions over multiple periods, in particular w.r.t. the equity of the allocation.

ABSTRACT. The COVID-19 pandemic has caused unprecedented damage to restaurant businesses, especially indoor dining services, due to the widespread fear of coronavirus exposure. In contrast, the online food ordering and delivery services, led by DoorDash, Grubhub, and Uber Eats, filled in the vacancy and achieved explosive growth. As a result, the restaurant industry is experiencing dramatic transformations under the crossfire of these two driving forces. However, these changes are not fully exposed due to the lack of first-hand data, let alone their potential consequences and implications. This study thus leverages foot traffic data to reveal and understand the trends of restaurant service demand through the pandemic. We develop a probabilistic learning model to decompose the aggregate foot traffic by dwelling time patterns into dine-in and takeout volumes. The transitions of demand structures are then identified for various restaurant sections by service types, price levels, and locations. We observe that limited-service and budget restaurants saw a significantly more speedy recovery than full-service counterparts, given their comparative advantages in adapting toward takeout channels. But in the long run, our results suggest the preserved demand for dine-in services at full-service restaurants, particularly those that provide more premium dining experiences. Comparatively, the offline channels at limited-service restaurants appeared vulnerable to the cannibalization from online ordering and delivery channels, which strengthened even after the society moved out of lockdown. Regionally, exurban restaurants seem to trend toward the takeout mode, while urban areas did not see a notable modal migration between dine-in and takeout from restaurants.

ABSTRACT. Local delivery platforms are collaborative undertakings where local stores offer instant-delivery to local customers ordering their products online. Offering such delivery services both reliably and cost-effectively is one of the main challenges for local delivery platforms as they face a complex, stochastic, dynamic pickup-and-delivery problem. Orders need to be consolidated to increase the efficiency of the delivery operations and thereby enable a high service guarantee towards the customer and stores. But, waiting for consolidation opportunities may jeopardize delivery service reliability in the future, and thus requires anticipating future demand. This paper introduces a generic approach to balance the consolidation potential and delivery urgency of orders. Specifically, it presents a newly developed parameterized Cost-Function Approximation (CFA) approach that modifies a set-packing formulation with two parameters. This CFA approach not only anticipates future demand but also utilizes column generation to search the large decision space related to pickup-and-delivery problems fast. Inspired by a motivating application in the city of Groningen, the Netherlands, numerical experiments show that this CFA approach strongly increases perceived customer satisfaction while lowering the total travel time of the vehicles compared to various benchmark policies. It also reduces the percentage of late deliveries, and the extent of their lateness, to a minimum. Finally, the CFA approach may assist decision-makers in practice to manage the non-trivial balance between consolidation opportunity and delivery urgency.

ABSTRACT. This paper proposes a novel heuristic to solve the offline pickup and delivery problem with time windows (PDPTW), the classical combinatorial optimization problem in the transportation and logistics society. PDPTW is a NP-hard problem that has proven to be very challenging computationally. We propose the rolling horizon framework utilizing a state-of-the-art online PDPTW solver, which provides a better trade-off between computational efficiency and solution quality. To the best of our knowledge, this is the first attempt to solve offline PDPTWs using such a temporal decomposition scheme. To show the performance and scalability of our framework, we compare our results with an offline heuristic algorithm using Google OR-Tools. In real-world problem instances having approximately 2,500 requests, our framework can provide good solutions, while the baseline algorithm often fails to find a feasible solution within comparable compute times. To show the empirical evidence of the optimality gap, we compare our results with a modified Lin-Kernighan-Helsgaun heuristic (LKH3) which is recognized to find the best-known solution in artificially created benchmark instances. The optimality gap is around 6-13%, but the computation time is 20-80 times faster. In conclusion, the rolling horizon framework is more applicable to practice than the benchmark solvers since the suggested framework is scalable and computationally efficient with desirable solution quality. It can be also used to obtain a good initial feasible solution quickly and to subsequently improve the solution as time permits, combined with other local search heuristics.

ABSTRACT. Regarding the increasing trend in online purchases, local stores see a need to develop new strategies to remain competitive with the online retailers. Therefore, a range of local retailers starts offering a same-day delivery service to their customers who's demands with respect to delivery standards are constantly rising. Such services focus on the local market, promise a delivery within a few hours, and often use micro-hubs for intermediate storage and consolidation of parcels. This consolidation opportunity also allows collaboration among different storekeepers for joint delivery of parcels to the same region within the city. For this, we assume that storekeepers bring a parcel to the closest micro-hub as soon as the order is placed. Similarly, the customer picks up the parcel at the final micro-hub. A local fleet of emission-free vehicles then consistently visits the micro-hubs for pickup and delivery of parcels. This allows planning reliability for stores and drivers, and improves service quality for customers. We develop a two-stage stochastic program based on a time expanded network formulation. The model is solved to optimality with Gurobi on instances with 25 scenarios and 100 customers. We contrast our approach to a fixed consistent route, and a non-consistent upper bound. We find that our approach significantly outperforms the fixed solution and allows to implement consistent routes at low cost if compared to a non consistent, daily re-optimized routing.

ABSTRACT. Given a certain number of areas of interest on Earth, the objective of an ISR (Intelligence, Surveillance, and Reconnaissance) mission is to maximize the information gain from these areas using different sensors on available satellites. Various constraints exist, such as weather constraints, energy constraints, and feasibility constraints. The goal of this project is to identify which sensors on which satellites should collect data from which cells at which times to maximize information gain. However, information is not only gained from cells where data is directly collected from; data fusion techniques can be used to collect information from other cells as well. We use a spatial interpolation method called Kriging for data fusion. Using Kriging, the estimated error of the prediction in each cell can be calculated. We can say a cell is "confidently covered" if this estimated error is below a certain acceptable level. Since we have a limited amount of energy, we do not always need to transmit high-resolution data back to earth. So, we also decide how much the resolution of collected data should be reduced before transmission. In conclusion, we create an optimization model that decides (i) what data should be collected, from where, and when and (ii) how much the data should be compressed before transmission such that the number of "confidently covered" cells in high interest areas is maximized.

ABSTRACT. We study a system in which a common delivery fleet services both same-day delivery (SDD) and next-day delivery (NDD) orders placed by price-sensitive e-retail customers, focusing on two objectives. Motivated by empirical marketing research, we first consider customer satisfaction by maximizing the quantity of NDD orders fulfilled one day early. Next, we consider total profit by optimizing static prices in a two-level scheme with discounts for early-ordering customers. Our analysis relies on continuous approximation techniques to capture the interplay between NDD and SDD orders, and particularly the effect one day's operations have on the next, a novel modeling component not present in SDD-only models; a key technical result is establishing the model's convergence to a steady state. We derive structural insights and efficient algorithms for both objectives. In particular, we show that, under certain conditions, the total profit is a piecewise-convex function with polynomially-many breakpoints that can be efficiently enumerated. We validate our model's results via simulation on instances derived from real-world road networks.