ABSTRACT. We propose a new dynamic order-picking policy to synchronize collaborative robots (cobots) with stochastically arriving in-store customers and dedicated pickers to fulfill online orders from retail stores. While emerging research has considered cobots for order picking in distribution centers, where both cobots and pickers are controllable, we capture in-store customers' uncertain arrivals and behaviors. We modeled the problem as a Markov Decision Process and proposed a heuristic approach to govern the item assignments and routing decisions for picking resources. Experiments show the potential to offset the high requirements for human picking resources while meeting high demands and commitments for curbside pickup and home delivery services.

ABSTRACT. The small parcel delivery industry has grown significantly over the last few years. From an economic perspective, logistic operations in urban areas, notably last-mile delivery, tend to be the most expensive segment of the logistic process. In this study, we adopt a novel framework to economize the delivery of small parcels using the Physical Internet concept. We consider a hyper-connected network of service points, where each point can be served by more than one vehicle route, and parcels may be transferred from their origin to their destination in several legs. We present a method to route and schedule the parcels while considering the service times of the vehicles at the SPs. As a first step in analyzing this intricate problem, our model assumes that the routes of the vehicles are fixed and determined in advance. In particular, we present a dynamic routing policy for the parcels in a given network and a search algorithm to accomplish the vehicle scheduling. A preliminary experiment demonstrated the merits of this approach.

ABSTRACT. We study a pickup-and-delivery problem arising from the case in which a delivery platform serving a consortium of businesses receives customer requests stochastically throughout the day and fulfills these requests with a fleet consisting of both dedicated vehicles and crowdsourced drivers. Considering an objective that considers travel and delivery costs as well as lateness charges, we develop a cost function approximation to guide the assignment of requests to the two different types of delivery vehicles. Our computational results demonstrate the effectiveness of the cost function approximation relative to a myopic assignment approach. Through computational experiments, we also investigate the impact of marketing mechanisms that create opportunities for n-to-1 and 1-to-n bundling in the pickup-and-delivery problem.

ABSTRACT. We consider the sequential decision-making problem of making proactive request assignment and rejection decisions for a profit-maximizing operator of an autonomous mobility on demand system. We formalize this problem as a Markov decision process and propose a novel combination of multi-agent Soft Actor-Critic and weighted bipartite matching to obtain an anticipative control policy. Thereby, we factorize the operator's otherwise intractable action space, but still obtain a globally coordinated decision. Experiments based on real-world taxi data show that our method outperforms state of the art benchmarks with respect to performance, stability, and computational tractability.

ABSTRACT. From commercial optimization software, logistics providers expect high-quality solutions for complex real-world last-mile routing problems. Higher user satisfaction can be achieved by generating route plans fast and in an understandable way. We propose a scalable, clustering-based heuristic for solving large-scale vehicle routing problems (VRPs) in real-time. Clustering models are used to divide the large-scale VRP instance into multiple, less complex subproblems that are solved independently. The clustering information is integrated into a local search algorithm to merge the individual solutions into the overall route plan. Our computational experiments show that, for real-time applications, the proposed approach outperforms state-of-the-art metaheuristics such as the HGS-CVRP. Moreover, the results are easier to interpret through the additional information gained from the clustering.

ABSTRACT. Technological development has opened the door for "Autonomous Mobility-on-Demand" (AMoD) systems. Safe and reliable operation of autonomous vehicles requires detailed maps of roads generated by advanced sensors and computer vision. A major difficulty of the mapping process is that road conditions constantly change, e.g., by adding crosswalks or removing lanes. AMoD systems address this by updating the maps using real-time data collected by AVs in operation. An AV's knowledge and confidence in driving on a previously mapped road decrease over time as the road network is expected to evolve unless the road is "relearned" constantly. Operationally, an important trade-off ensues from relearning - while routing users along the fastest (and most familiar) routes minimizes travel times, detouring traffic along less-utilized routes ensures relearning of the road network. Such detours not only increase travel time by increasing distance but also by lowering travel speeds on road segments that the AV is less confident traversing (thus the need for relearning) and can lead to user dissatisfaction. Motivated by this important problem, we study (i) the impact of relearning on service profitability and availability and (ii) to which extent user equilibria deviate from the platform-optimal solution. We model the steady-state problem of the AMoD operator using a fluid approximation considering learning-dependent travel times and cast this problem into a mixed-integer second-order cone program to conduct extensive numerical experiments. Further, we analyze the behavior of selfish users of the system, using an iterated best response algorithm to determine user equilibria.

ABSTRACT. This study considers the heavy-duty truck electrification problem with charging infrastructure decisions (TEPI) for short-distance trucking operations in container terminals. Using the trajectories of the trucks derived from historical GPS-tracking data, we formulate the TEPI as a mixed-integer linear programming model (MILP). To solve the problem on a realistic scale, we propose a Benders decomposition algorithm. Extensive experiments using instances generated based on real-world operations in a large container terminal were conducted. The results demonstrate that the Benders decomposition algorithm can adequately solve large-scale problems and that the electrification of trucks can contribute to significant reductions in operational costs and greenhouse gas (GHG) emissions.

ABSTRACT. The fixed charge transportation problem (FCTP) is a generalization of the well- known transportation problem, which also has a fixed cost of transportation between any source and destination, besides the variable cost per unit of transportation. Instead of a pure linear programme for the transportation problem, the presence of the fixed cost leads to a mixed-integer linear programme (MILP) based model for FCTP. Hence, while the transportation problem is polynomially solvable, FCTP is known to be NP-hard.

One way to solve FCTP more efficiently is by improving its lower bound using valid inequalities, also known as cutting planes. In this paper, we propose a new class of valid inequalities based on the idea of partitioning of a cover for the knapsack polytope. We further provide conditions under which they define facets of the knapsack polytope. Through computational experiments, we demonstrate the efficacy of our proposed valid inequalities in solving the FCTP.

ABSTRACT. In long-haul freight transportation, joint vehicle routing, and driver scheduling problem have been well studied for diesel-powered trucks. This study is among the first to study the feasibility of electric truck (e-truck) routing in long-haul freight transportation. This paper proposes a mathematical model, the electric truck routing and driver scheduling problem with coordinated charging scheduling (eTRDSP-CS), to determine e-truck routing and driver's work schedule, which synchronizes the charging schedule of e-truck. The total operating cost of the eTRDSP-CS is formulated from the perspective of the truck fleet owner and accounts for driver's payment for payable time, electricity cost and penalty cost for unpunctual arrival at customers. We present the framework of the eTRDSP-CS and conduct a numerical experiment using an inter-city highway corridor from Chicago to Atlanta. We also compare the performance with the diesel truck. The results imply that rest areas and truck stops along the highways are promising candidates for charging stations for long-haul e-trucks. The findings also suggest that long-haul e-truck takes an expected longer time (~20% longer) to finish the journey than diesel truck due to charging, but saves much more (about 60%) in terms of the total operating cost.

ABSTRACT. Ride-sourcing companies have been widely using threshold-based incentive programs to encourage drivers to extend their working hours. In such programs, a driver receives a certain amount of monetary reward if she completes a given supply task within a predetermined time window. However, despite the popularity of these incentives, little is known about how drivers respond to them in practice, and currently, there is no means to evaluate and optimize their designs systematically. To fill the void, we develop a dynamic discrete choice model that formulates ride-sourcing drivers' working decisions influenced by threshold-based incentives and then calibrate it using real-world data from a ride-sourcing company. Our results provide fresh insights into the market and welfare effects of the threshold-based incentive and its various designs. It is found that the threshold-based incentive could increase welfare significantly for full-time drivers but marginally for part-time drivers. In contrast, involving part-time drivers in the incentive programs generally can yield higher profits for the platform, while incentivizing full-time drivers is mostly unprofitable. On incentive design, the incentive threshold and reward must be closely paired for different driver groups to avoid inferior consequences for the platform and drivers. In addition, switching from threshold-based incentives to direct wage increments may benefit both certain full-time drivers and the ride-sourcing company.

ABSTRACT. The inefficient first-mile connection is a key factor preventing riders from using the public transportation system. Some riders would switch to other modes of transportation, such as taxis or private cars, which is uneconomical for riders and tricky to hail a taxi during rush hours. Therefore, it is imperative to close the first-mile gap with high-quality and affordable transit services. In this study, we propose a first-mile service mode in which public transit agencies can integrate privately-owned autonomous passenger cars with idle time to provide on-demand first-mile ridesharing services. The objective for public transit agencies is to minimize the total operational cost while considering the ready time of cars, the location and latest return time of private autonomous cars, as well as riders’ service quality requirements. To determine scheduling schemes of the cars and ridesharing schemes of the riders, a branch-and-price exact algorithm is developed. The algorithm can solve most instances to optimality but with a relatively long computation time. Furthermore, a tailored column generation matheuristic algorithm is introduced to yield high-quality solutions in less time. Numerical experiments demonstrate the effectiveness of the proposed models and algorithms and show that the ridesharing service can provide low-cost, high-quality solutions to the first-mile travel problem.

ABSTRACT. Dynamic pricing has been widely studied as an effective and profitable way for addressing the geographical supply-demand mismatches in carsharing systems. Such dynamic prices are mostly optimized on a zonal basis, which is typically defined as a prior or independent of pricing decisions. Methods that simultaneouly define a business area partition and pricing strategy are, to our knowledge, absent. In this article we present a comprehensive carsharing pricing and zonification model, which entails paritioning the business area into pricing zones as well as defining trip prices between the zones created to maximize the profitability of carsharing services. We formulate the problem as a mixed-integer linear program. An ad-hoc Benders decomposition algorithm is developed to handle large-scale instances. Preliminary results illustrate the effectiveness of pricing zonifictaion strategy in ensuring profitability of carsharing operators. Particularly, in the scenario with 4 pricing zones, the hourly profit of a carsharing system with 20 stations and 40 customers increases by around 29.4% compared to the scenario without pricing zone partitions.

ABSTRACT. Operational planning at transshipment nodes is a wide and challenging field of research that covers a vast number of distinct relevant applications, spanning from seaport container terminals to rail terminals to cross-docks. In this work, we study the feasibility version of a fundamental synchronization problem that assigns incoming vehicles to docking resources subject to handover relations. We carry out a comprehensive analysis of computational complexity of various problem variants and establish structural connections to famous decision problems in graph theory.

ABSTRACT. Increasing efficiency in roll-on roll-off terminals offers potential for more sustainability. Our work focuses on the unloading and loading process of the vessel with dual cycling employed to increase efficiency. We consider a deterministic, time-continuous linear optimization model with precedence constraints to minimize the vessel’s turnaround time. As a result, we allow the ship to depart earlier and travel slower, consuming less fuel.

ABSTRACT. The decarbonization of the US transportation sector presents a considerable challenge for energy intensive transportation services with cyclic operations on expansive networks, e.g., freight rail and trucking and intercity bus services. We present a sequential framework to address the problem of deploying the refueling infrastructure required by alternative fuel propulsion technologies on transportation networks. The framework consists of two optimization problems to locate and size (i.e., specify the capacity of) service facilities on existing transportation networks and a traffic assignment problem that routes flows on the resulting subnetwork enabled by the selected facilities. To illustrate the framework we consider the deployment of battery-electric locomotives and charging facilities on an aggregate national network of three Class I railroads. We formulate a new variant of the flow-based set cover problem for transportation applications that engage in asset repositioning and demonstrate its relevant properties in the context of general facility location problems. Relative to current diesel emissions estimates, the scenario considered leads to a 36% emissions reduction under the current electric grid scenario and an 84% decrease in emissions in a renewable electric grid case. Our framework runs extremely efficiently and provides interpretable results at every step of the process. This framework also offers significant modeling flexibility as components can be altered to capture different deployment objectives or operational considerations.

ABSTRACT. Microtransit offers opportunities to enhance urban mobility by combining the reliability of public transit and the flexibility of ride-sharing. This paper optimizes the design and operations of a demand-responsive microtransit system that relies on reference lines and performs on-demand deviations in response to passenger demand. We formulate a Microtransit Network Design (MiND) model via two-stage stochastic optimization. The model features a tight second-stage formulation thanks to a subpath-based representation of microtransit operations in a load-expanded network, which optimizes on-demand deviations between checkpoint stops. We develop a double decomposition algorithm combining Benders decomposition and subpath-based column generation armed with a tailored label-setting algorithm. Using real-world data from Manhattan, results suggest that our method scales to large practical instances, with up to 100 candidate lines and hundreds of stops. Comparisons with transit and ride-sharing benchmarks suggest that microtransit can provide win-win outcomes toward efficient, equitable and sustainable mobility: high demand coverage, low operating costs, high level of service, broad geographic reach, and limited environmental footprint.

ABSTRACT. Column generation is applied within branch-price-and-cut algorithms for solving a wide variety of vehicle routing problems. It often exhibits slow convergence due to high degeneracy in the master problem. To accelerate convergence, dual inequalities, which are specific to the model considered, can be employed. In this paper, we consider simple dual inequalities that can be applied to all models. To identify them, we propose to use a machine learning model, namely, a graphical neural network that may be inaccurate and lead to weaker lower bounds. We test this acceleration strategy on a multi-depot electric vehicle scheduling problem arising in public transit. Preliminary computational results show an average speedup of 3.6 at the expense of an average decrease of 0.97% of the lower bound. A recovery procedure can, then, be applied to improve the lower bound. Complete results will be presented at the conference.

ABSTRACT. We propose a novel dynamic vehicle dispatch problem with holding costs (DVDPHC), which is relevant for many practical applications, such as solid waste collection, food and blood bank collection, and dairy collection. In DVDPHC, which integrates dynamic vehicle dispatch, routing, and loading/unloading decisions, a limited-capacity vehicle must collect perishable products from geographically dispersed locations that produce in uncertain quantities, and return them to a depot. To effectively solve this problem on instances of realistic size, we propose an approximate dynamic programming approach with a neural network (ADP-NN). Extensive numerical experiments demonstrate that our ADP-NN framework is fast, scalable and robust. In realistically-sized problem instances, ADP-NN matches or outperforms a dynamic look-ahead (DLA) approach in terms of total holding and travel cost in 66 of the 120 instances, while achieving an average 12.77% improvement in the total cost. Numerical analysis reveals that our proposed ADP-NN procedure exhibits complex self-learned flexible behavior.

ABSTRACT. We focus on the capacitated version of the dynamic Vehicle Routing Problem with Time Windows (VRPTW), a combinatorial optimization problem with uncertainty of future customers. To find an efficient routing policy for this problem, we introduce a novel Machine Learning enriched Combinatorial Optimization pipeline. Specifically, we decompose the dynamic VRPTW into a Prize-Collecting VRPTW so that we only dispatch a customer when its prize is above the costs of serving this customer. As this prize is unknown, we use Machine Learning to predict these prizes. The policy we encode via this pipeline decreases routing costs by 16.69 percentage points in comparison with a greedy routing policy and only has an average gap of 4.43% to the best known routing solution.

ABSTRACT. The steady growth in e-commerce and grocery deliveries within cities puts a strain on the available infrastructure in urban areas by increasing the total number of freight movements, aggravating traffic congestion, as well as air and noise pollution. In this context, this research introduces the \textit{Two-Echelon Prize-Collecting Vehicle Routing Problem with Time Windows and Vehicle Synchronization}, where deliveries are carried out by smaller low- or zero-emission vehicles as well as larger trucks. Given their capacity restrictions, the smaller vehicles can only deliver small-sized orders and have to be replenished via depot locations or larger-sized trucks. Besides replenishing smaller vehicles at satellite locations, larger-sized trucks can deliver both small-sized orders as well as larger items. Managing these two types of fleets in an urban setting under consideration of capacity limitations, tight delivery time windows, vehicle synchronization, and selective order fulfillment is challenging. We model this problem on a time-expanded network and apply network reduction by considering the time window constraints. In addition, we propose a branch-and-price algorithm that is capable of solving instances with up to 200 customers and continuously outperforms a state-of-the-art general-purpose optimization solver. Moreover, we present several managerial insights concerning the use of synchronization, vehicles, and the placement of depot/satellite locations.

ABSTRACT. We propose a new exact method for the capacitated multi-trip vehicle routing problem with time windows (CMTVRPTW). The problem has wide practical applications, as it allows each vehicle to perform more than one trip to serve customers. The multi-trip characteristic, however, makes the problem very challenging to solve. Only 14 of the 27 benchmark instances with 100 customers have been solved to optimality in the existing literature. Our new exact method novelly utilizes two set partitioning-like formulations of the CMTVRPTW. It has solved all the existing benchmark instances with 100 customers to optimality for the first time in the literature.

ABSTRACT. We introduce several variants of the well-known Hub Location Problem, based on tree topology. In particular, we introduce the notion of stopover nodes, which are possible intermediate stops between hubs. The introduction of these nodes contributes to reduce the overall distance traveled by vehicles, but may also increase the transportation time between hubs.

We model several variants of tree-based hub location problems with stopovers and present the result of extensive computational experiments.This work is applied to the context of the implementation of the Physical Internet concept on waterways.

ABSTRACT. Credit-based congestion pricing (CBCP) has emerged as a mechanism to alleviate the social inequity concerns of road congestion pricing - a promising strategy for traffic congestion mitigation - by providing low-income users with travel credits to offset some of their toll payments. While CBCP offers immense potential for addressing inequity issues that hamper the practical viability of congestion pricing, the deployment of CBCP in practice is nascent, and the potential efficacy and optimal design of CBCP schemes have yet to be formalized. In this work, we study the design of CBCP schemes to achieve particular societal objectives and investigate their influence on traffic patterns when routing heterogeneous users with different values of time (VoTs) in a multi-lane highway with an express lane. We introduce a new non-atomic congestion game model of a mixed-economy, wherein eligible users receive travel credits while the remaining ineligible users pay out-of-pocket to use the express lane. In this setting, we investigate the effect of CBCP schemes on traffic patterns by characterizing the properties (i.e., existence, comparative statics) of the corresponding Nash equilibria and, in the setting when eligible users have time-invariant VoTs, develop a convex program to compute these equilibria. We further present a bi-level optimization framework to design optimal CBCP schemes to achieve a central planner’s societal objectives. Finally, we conduct numerical experiments based on a case study of the San Mateo 101 Express Lanes Project, one of the first North American CBCP pilots. Our results demonstrate the potential of CBCP to enable low-income travelers to avail of the travel time savings provided by congestion pricing on express lanes while having comparatively low impacts on the travel costs of other road users.

ABSTRACT. The increase in e-commerce sales has put a spotlight on the last-mile portion of the order fulfilment process, which can represent up to 50% of total logistics costs. E-commerce has also played a major role in the significant increase in the number and size of fulfillment centers and warehouses; order picking is of similar importance within these facilities, accounting for up to 55% of operating costs. A common element in many processes within an e-commerce supply chain, including same-day delivery (SDD), order picking and shelf re-stocking, is the need to dispatch (i.e. deliver, process, pick or re-stock) orders or items that become available at different times, but where batching yields economies of scale in dispatching time. We model the tension between those elements and focus on the case of many identical vehicles.

ABSTRACT. Motivated by continuously evolving education environments and operations research advances, we revisit the school district design problem. We introduce a new compact formulation that incorporates multiple decisions simultaneously by assigning students in each geographic unit to a set of schools (e.g., elementary, middle, high schools, and schools with special programming) with a single composite variable, referred to as a "stream." This compact formulation incorporates advances in district design modeling from the literature and extends the decision-making capabilities of such models. We tie these extensions to education literature and policies at specific school districts. This new formulation is computationally efficient, easily reconfigurable for evolving problem specifications, and facilitates improved communication with stakeholders. To illustrate these capabilities, we present a case study from a partnership focused on district redesign to address historical inequities in access to education.

ABSTRACT. Motivated by a collaboration with the San Francisco Unified School District (SFUSD), this paper presents an interactive optimization framework for addressing complex public policy problems. These problems suffer from a chicken-and-egg dilemma, where policymakers understand the objectives and constraints but lack the ability to solve them ("the optimization problem"), while researchers possess the necessary algorithms but lack the necessary insights into the policy context ("the policy problem"). Our framework addresses this challenge by combining three key elements: (1) an efficient optimization algorithm that can solve the problem given certain known objectives, (2) a method for generating a large set of diverse, near-optimal solutions, and (3) an interface that facilitates exploration of the solution space. We illustrate the effectiveness of this framework by applying it to the problem of improving school schedules at SFUSD. The resulting schedule, implemented in August 2021, saved the district over $5 million and, to our knowledge, represents the first successful optimization-driven school start time change in the United States.

ABSTRACT. To better match drivers to passengers in our ridesharing application, we overhauled Lyft’s core matching component using a novel reinforcement learning approach. This innovation enabled our drivers to serve millions of additional rides each year, leading to more than $30M per year in incremental revenue. This change was the first documented real-world implementation of a ridesharing matching algorithm that can learn and improve in real-time. Experiments showed that this approach benefits drivers, passengers, and the platform.

ABSTRACT. Parcel lockers are emerging as a viable alternative to traditional home delivery: When ordering goods online, customers can specify a locker instead of their home as their desired delivery address. Because the lockers are fully automated, they enable customers to pick up their parcels at any time within a given number of days. Therefore, customers benefit from increased flexibility in receiving their parcels. From the logistics service provider’s point of view, parcel lockers offer a huge cost reduction potential resulting from consolidation and fewer failed delivery attempts. To fully exploit this potential and simultaneously ensure customer satisfaction, however, successful management of the locker’s capacity is crucial. Basically, this requires that an appropriately sized compartment must be available for each customer’s parcel from the time of delivery up until the customer collects their parcel from the locker. This is challenging because future delivery requests, the associated parcel sizes, and pickup times are stochastic from the provider’s perspective. In this talk, we show that demand management may act as a valuable tool to maximize the number of served customers and effectively utilize scarce locker capacity. Firstly, we present the resulting sequential decision problem and highlight its main properties. Secondly, we outline an anticipatory solution approach. Thirdly, we conclude our talk with results from our computational tests that demonstrate the value of anticipation for this problem.

ABSTRACT. See attached

ABSTRACT. Relay logistics decompose origin-destination shipments into short segments through a pit-stop network, traveled by separate drivers. This paper optimizes the routing of orders, drivers and vehicles via a Relay Pickup-and-Delivery Problem (RPDP), formulated as an integer optimization model across coupled time-space networks. To solve it, we develop a new column-set-generation algorithm that iterates between a sparse master problem (which fixes variables to zero, i.e., ignores some time-space arcs in the RPDP) and a multi-variable subproblem (which seeks a deviation of negative reduced cost within a relaxed and projected polyhedron, i.e., a path with negative reduced cost in the RPDP). We prove that the algorithm converges finitely to an optimal solution in linear optimization. It augments column generation by leveraging primal feasibility conditions to generate multiple "synergistic" variables at a time, and to guarantee optimality when some variables have a negative reduced cost. Using real-world data from Rivigo, the multi-variable algorithm terminates much faster and scales to larger instances than several benchmarks. Practically, our modeling and algorithmic approach can provide win-win outcomes in relay logistics: better driver lifestyles, better customer service, lower operating costs, and a smaller environmental footprint.