ABSTRACT. A fundamental situation every passenger railway operator has to face is to offer an attractive railway timetable to the passengers while operating it as cost efficient as possible. Thus available rolling stock has to be assigned to trips so that all trips are operated, operational requirements are satisfied, and the operating cost are minimum. This is called the Rolling Stock Rotation Problem. This problem is well studied in the literature for example in Fioole et al. (2006) or Cacchiani et al. This paper deals with the rolling stock rotation problem with integrated vehicle maintenance. The approaches presented here are based on the work of Borndoerfer et. at.(2016). A novel IP model is presented that makes use of maintenance path for the vehicles that were linked to hyperarcs that model vehicle compositions. To solve the model different column generation procedures were implemented. The different procedures were evaluated on real world instances. Finally, they were compared with each other and the algorithm of Borndoerfer et. at.(2016) in terms of runtime and solution quality. Submitted

ABSTRACT. We present a new mathematical formulation for tactical railway timetabling that aims at minimizing total passenger perceived travel time. This new formulation, based on the POT formulation by Polinder et al. (2021), relaxes the generally adopted assumption that line frequency is given as input and considers instead a minimum and maximum frequency. We provide experimental results displaying insights on the cost of fixed frequencies, and demonstrate that fewer trains might lead to better timetables in heavily utilised networks. We further aim at developing heuristics to scale up the applicability of the model to large instances.

ABSTRACT. Attendance rates decrease personnel costs of conductors or board service personnel by defining only a percentage of trips that must be accompanied. Based on real-world data from German regional passenger transport, we analyze the impact of different attendance rate policies on the respective objectives in railway operations, i.e., the share of attended trains, the service level, and the caught fare dodgers. For this, a column generation approach is used. The results can provide guidelines for transport associations to define suitable attendance rates.

ABSTRACT. This study focuses on investigating the tactical planning of an integrated multi-stakeholder system. The system receives time-dependent requests from carriers and shippers and optimizes in time and space the operations and transportation activities through the consolidation of loads of different shippers into the same vehicles. The demand values of shippers are taken under uncertainty. The aim of tactical planning in this system is to build an efficient service network and schedule to satisfy the demand and requirements of shippers by making use of the predicted services and their capacities offered by the carriers. A two-stage stochastic program is presented and an exact decomposition-based algorithm is developed. Extensive computational analysis is performed to evaluate the impact of uncertainty on the solution of the proposed model.

ABSTRACT. Continuing growth in urbanization and e-commerce results in more package deliveries in urban areas. Although some carriers are well-consolidated and have efficient distribution operations, the number of delivery vehicles carrying loads less than vehicle capacities is progressively increasing in cities as a result of uberification. These ultimately turn into challenges for cities such as increasing traffic congestion and noise pollution. In this work, we aim to guide authorities in making freight transport more sustainable in logistically complicated small cities, where reasonably robust answers may not be drawn from the existing literature (which mainly deals with large cities). We focus on the authorities’ role and predict carriers’ behaviors (measured by distance and stops) as a reaction to alternative freight policies the authorities could impose. In this regard, we propose a routing-based framework as a policy guidance tool and analyze different regulatory structures based on real maps and real demand patterns from the City of Bergen, Norway.

ABSTRACT. The extended abstract is in the attached file.

ABSTRACT. In this work, we deal with a problem arising in a city logistics context in which a fleet of ground drones is used to service a set of requests in an urban area. The peculiarity is that, in addition to using sidewalks, the ground drones can autonomously ride on public-transportation vehicles (e.g., bus, train, or metro) as part of their routes, to reach customers that otherwise would have been too far, because of the battery duration. The goal is to find a set of routes of minimum total cost, such that each daily request is served by exactly one vehicle. In several metaheuristics for Vehicle Routing Problems, repair operators are applied to portions of the current solution chosen at random during the destroy phase. Instead, our main algorithmic contribution is the definition of a new mechanism, dubbed Destroy-and-Repair Propagation (DRP) that exploits the spatial structure of the problem. In this work, DRP is embedded into a Variable Neighborhood Descent (VND) framework. Our approach is tested on a set of instances derived from the urban area of Rome (Italy), resembling drugs distribution from a central depot to pharmacies. The results indicate that coordinating the sequence of destroy actions is valuable, especially when the number of customers becomes large.

ABSTRACT. Traffic congestion and high greenhouse gas emission rates are frequent criticisms of conventional urban last-mile transport. The integration of freight deliveries with the existing public transport infrastructure, e.g., light rail, is a promising example of related future concepts. In this work, a selection of public transit stops serves as micro-depots where freight transhipment processes take place, given a limited storage capacity. Additionally, we propose an optimisation model that integrates the tactical scheduling of cargo and passenger vehicles and the allocation of cargo to vehicles. The optimisation prioritises the passenger service by minimizing the passengers waiting time first. As a secondary objective, it minimises the number of rejections and the delivery delay of cargo requests. To solve realistically large instances, we propose an adaptive large neighbourhood search heuristic.

ABSTRACT. We study an Autonomous Mobile Robots (AMR) service. A set of delivery requests is given, where each request is characterized by a pair of pick-up and delivery locations as well as time windows during which service can begin in these locations. A fleet of robots is distributed among several depots in the service area. In order to extend the reach of the service, the robots are allowed to perform parts of their journey on board public transit vehicles. Specifically, the robots are boarded in a way that does not reduce the passenger capacity. A set of fixed public transit lines which operate in the service area are given. Each fixed line is characterized by a sequence of stations, the traveling times between them, and the frequency of the service. When a robot is assigned to a task, it needs to travel from its origin depot to a pickup point, then travel to the associated delivery point, and finally return to one of the depots for recharging. Each leg of this journey can be performed directly by the robot (using battery power), or be performed partially on board a public transit vehicle, which travels at a higher speed and does not require battery discharging.

We consider the static version of the operational problem and assume that all given requests must be served, either by the AMR’s or by an alternative service (outsourcing) at a greater cost. For each request the problem is to decide upon the means it will be served. Specifically, for requests served by the AMR’s, we need to decide which robot will be assigned to each request, the robots’ routes, and the depots to which they will return. This needs to be determined while respecting the maximal number of robots that can be carried simultaneously by a public transit service and the capacities of the robot depots. The goal of the decision problem is to minimize the total operational cost which is composed of the AMR’s operational costs and costs associated with the alternative service.

We develop arc-based and route-based formulations of the problem. The former represents explicitly each potential leg of the robots and decides upon the legs to be traveled. The latter considers complete feasible routes to select the best route (and robot) for each request. While the route-based formulation has a more compact structure, the number of routes that may be considered grows exponentially with the number of requests, thus this formulation can be solved directly by fully enumerating all potential routes only for very small instances of the problem. To handle medium to large instances we develop a column generation approach. We define an initial set of potentially good routes for each robot-request pair and then formulate the underlying sub-problem of finding new promising routes as a resource constrained shortest path problem. Based on the assumption that each robot serves at most one request during the planning horizon, we develop a five-stage dynamic programming algorithm to solve this problem. Furthermore, as the robot-request sub-problems are independent, we apply parallel computing to speed up each column generation iteration.

We have randomly generated six-hundred problem instances, consisting of 10 to 150 requests (and robots), 10 to 40 public transit nodes, and 5 to 70 depots. We have run the column generation framework with a default setting where in each iteration, all robot-request sub-problems are solved sequentially. Initial results show that with the arc-based formulation only instances with up to 15 requests can be solved to optimality within ten minutes while the route-based column generation approach can handle instances with up to 150 requests in less than five minutes. Though the path-based formulation does not have an integrality property, we observe that only 7% of the instances result with non-integral solutions. We directly solve these instances with the obtained column set while enforcing integrality, using a MILP solver. The average optimally gaps obtained for these instances is 0.8%.

ABSTRACT. Urban on-demand transportation services are booming in both passenger transportation and the transportation of goods. The types of service differ in timeliness and compensation and, until now, providers operate larger fleets separately for each type of service. While this may ensure sufficient resources for lucrative passenger transportation, the separation also leaves consolidation potentials untapped. Therefore, we propose combining both services in an anticipatory way that ensures high passenger service rates while simultaneously transporting a large number of goods. To this end, we introduce a dynamic priority policy that uses a time-dependent percentage of vehicles mainly to serve passengers. To find effective time-dependent parametrizations given a limited number of runtime-expensive simulations, we apply Bayesian Optimization. We show that our anticipatory policy increases revenue and service rates significantly, whereas a myopic combination of service may actually lead to inferior performance compared to using two separate fleets.

ABSTRACT. A common assumption in the stochastic vehicle routing literature is that each demand must be met exactly. However, in numerous practical situations, it is more important that all customers receive part of their demand, rather than some customers receiving their demand and others not receiving anything. This holds in particular for food rescue programs, humanitarian logistics and/or disaster relief, where the total demand is (often) larger than the supply. We propose a model that allows for partial deliveries and takes fairness considerations into account. The model is solved with branch and price. Results show that with partial deliveries, a similar service level as with chance constraints can be achieved, but at lower cost.

ABSTRACT. The efficient management of fleet and crew is extremely important for airline companies to reduce their costs and increase their revenue. In this work, a detailed mathematical model is presented for the integrated problem of airline fleet and crew scheduling. The uncertainty is considered in the availability periods of a proportion of aircraft and crew. A robust optimisation approach with a novel matheuristic algorithm consisting of particle swarm optimisation, simulated annealing, and mathematical programming of partial models is proposed. The performance of our solution methodology is examined on a set of real-based instances and also compared to a state-of-the-art algorithm.

ABSTRACT. A number of airline mergers in the early 2000s, changing economic conditions and recessions, and the impact of the COVID-19 pandemic have led to air service disparities across collocated airports within megaregions. As a result of these disparities, travelers seeking air travel may forgo their local, small airports for more favorable service at farther airports in a phenomenon known as airport leakage. The advent of emerging mobility and vehicle automation (e.g., connected and autonomous vehicles) has the potential to alter travelers’ commuting patterns and access/egress options to airport systems, thus impacting airport leakage patterns. Previous literature acknowledges - yet stops short of developing - models that incorporate emerging mobility options in estimating airport demand and related characteristics (e.g., airport catchment areas, leakage dynamics, etc.). In this work, we model the dynamic effects across time as individual census tracts choose to adopt, and thereby influence, the decision(s) of surrounding census tracts to adopt autonomous vehicles as an option for accessing airports. We cast this problem as a discrete-time agent-based simulation model where we first estimate airport leakage using a logit model structure and then dynamically update adoption probability parameters based on census-tract level influences. Preliminary numerical results using simulated air service and ground transportation data achieves convergence to an equilibrium of approximately 68% of passengers leaking from their local airport and substitute airport on nonstop itineraries. Due to this uneven and dynamic (re)distribution of airport demand, this model and study will guide airport managers and planning agencies in managing air service with growing adoption of emerging mobility, thus helping to mitigate negative local economic and traveler accessibility consequences.

ABSTRACT. The popularity and the market share of Electric Vehicles (EVs) are on the rise mainly due to developments in battery technologies and sustainability efforts. While the future for EVs looks bright, there are several obstacles before them conquer the market, limited driving autonomy and long charge times being the most significant ones. One way to overcome these obstacles with the state-of-the-art charging and battery technology today is to pre-determine a route with a minimum total waiting and charging time with the fewest number of stops. This gives rise to a shortest path problem from an origin to a destination through charging stations with probabilistic waiting times. The baseline solution is an Expected Value Solution, where Dijkstra’s Algorithm based on the expected waiting times is used to find a path. An improved solution is an Online Recourse policy that allows to detour to more viable paths in case of long waiting times, which are revealed upon arrival to charging stations. To improve upon that we proposed a cutting planes algorithm to find an initial path that exploits the online recourse actions. We investigated several policies to find initial path planning problem and compared them with EVS and online recourse performance. Our findings indicate that Online Recourse and Cutting-Planes based initial path planning provides significant cost advantage compared to heuristic based solution methods.

ABSTRACT. In this work we study the decision problem in which a company must perform, starting from its retail store, a set of deliveries to customers who purchased their orders online. The delivery can be performed either by traditional vehicles or by in-store customers, named occasional drivers,OD, who accept to perform them on their way back home. At fixed interval of time, the company generates bundles of customers to be offered to ODs. Each OD submit bids for all the bundles which he/she is interested to serve. The company decide which bids to accept. No information about future ODs arrivals is available. At the end of the time-horizon leftover requests must be served by traditional vehicles. The goal is to minimize the total cost for the company, expressed as the sum of the routing costs of the owned vehicles and the costs associated with the accepted bids. We investigate several bid acceptance policies and test them on benchmark instances. Results are compared with those obtainable solving an oracle problem, in which we suppose to have a perfect information on future ODs arrivals. We analyze the performances of the proposed policies and discuss strength points and drawbacks of each of them. Almost all the policies provide very good results and the best performing one is able to obtain results only 11% far from the oracle solution.

ABSTRACT. The abstract is at attachment 1. Motivation and Problem Formulation With the continue growth in E-retailing, online retailers are facing increasing pressure in making fast delivery. The growing popularization of crowdsourced delivery serves as a way to alleviate the challenges faced by the retailers. For instance, Amazon flex hired crowdsourced drivers to deliver online orders. Drivers can either use their own vehicles or rent vehicles from car-sharing companies to provide delivery services. While more and more car-sharing companies are employing electric vehicles in their business (Manthey 2020, Woods 2022), we investigate a crowdsourced delivery problem in which crowdsourced drivers rent electric vehicles to deliver orders for an online retailer. We assume that crowdsourced drivers will send out their work applications when they are available to provide delivery services. The period of time during which the drivers are available are specified in their work applications. We assume that the arrival time of each driver in the system is uncertain, so does the driver’s available working duration. Upon the arrival of a driver, the retailer needs to decide whether or not to hire the driver. If hiring a driver, the system will then assign the driver to a nearby rental station, where the driver can pick up the electric vehicle reserved for her. The battery level of the vehicle that can be reserved for a driver is uncertain. We assume that each hired driver will be assigned to pick up a vehicle from a rental station close to the driver’s original location, while the battery level of the vehicle is above a threshold and is the highest in the station. After picking up the electric vehicle, the driver will head for the warehouse to pick up the packages.

We assume that customer orders arrive stochastically into the system. Each order needs to be scheduled for delivery by the end of the system’s operation time horizon. Upon the arrival of an order, the system will decide which driver to assign the order to. The number of customer orders that can be assigned to a driver depends on the driver’s available working duration as well as the energy level of the vehicle used by the driver. If there are no drivers available when an order arrives, the order will be put into a waiting list. If the system fails to hire enough crowdsourced drivers and there are still orders unscheduled for delivery at the end of the time horizon, third party drivers will be hired to deliver orders at higher costs. Therefore, drivers will wait at the warehouse for being assign as many orders as possible, until their working duration limit is reached or their vehicles’ battery level cannot route to anymore customers, or till the end of the time horizon. We assume that after finishing delivering all orders in her route, each driver will return the electric vehicle to the rental station closest to the last customer in the route and then go off work.

We formulate the problem as a Markov decision process (MDP) model. The state of the system includes the current time, the set of unassigned orders, the information on each hired driver (the remaining working duration of the driver, the battery level of the vehicle used by the driver, the set of orders assigned to the driver), and the information on the drivers whose work applications are neither accepted or rejected (new drivers’ working duration and initial locations). we assume that a decision epoch is triggered by the arrival of a crowdsourced driver in the system. At each decision epoch, the actions need to be taken are whether to hire a newly arrived driver, which orders to assign to all the hired drivers, and how to route the drivers to deliver orders. Between two decision epochs, the information on the newly arrived drivers, the available electric vehicles’ battery levels, and newly arrived customer orders are observed. We assume that there is only one driver arriving at each decision epoch. We consider that an hourly salary is paid to the hired crowdsourced drivers and a per-order fee is paid to the third-party dedicated drivers for delivering unassigned orders at the end of the horizon. The objective of the MDP model is to minimize the total expected costs over the entire horizon.

2. Solution Approach Due to the curse of dimensionality presented in our model, we are not able to find optimal policies via backward dynamic programming approach. Instead, we propose heuristic methods to solve the problem. Specifically, we develop a marginal cost balancing heuristic to make driver recruitment decisions and implement a routing heuristic to develop routes for hired drivers. In the marginal cost balancing heuristic, we balance the costs of hiring “too many” or “too few” crowdsourced drivers. Because there are uncertain customer demands and battery levels of rented electric vehicles, we will either hire “too many” and “too few” crowdsourced drivers. Hiring too many crowdsourced drivers may result in paying too much salary to the drivers while we may not be able to use up all the available working hours from them. Hiring too few crowdsourced drivers may result in delivering too many orders via third party drivers at greater costs. Let c_h represent the hourly salary paid to a crowdsourced driver. Let m represent the driver whose arrival has triggered decision epoch k. Let l_m represent the available working duration from driver m. We assume that once deciding to hire a driver, the system will purchase all the available working hours from the driver. Let a_h ∈ {0, 1} represent the decision of whether or not to hire a driver. Given action a_h at decision epoch k, it is possible that even if we do not hire any drivers from decision epochs k+1 through ρ−1, there are still unused capacity available from the hired drivers at decision epoch ρ(ρ ≥ k +1). Let H_k(a_h) represent the hiring costs (salary paid to drivers) resulting from the recruitment decision made at decision epoch k. We have H_k(a_h)= c_ha_hl_m. (1) Let M represent the set of hired drivers before taking an action at decision epoch k. Let I_k represent the information on the drivers in set M. Let ω_m represent the battery level of the vehicle that can be used by driver m if the driver is hired at decision epoch k. Let Θ_k represent the set of unassigned orders before making decision at decision epoch k. Let D_k represent the set of customer orders that have arrived in the system between decision epoch k−1 and k. Let D(I_k, a_hl_m,ω_m,Θ_k) represent the number of orders that are assigned for delivery after making decision at epoch k. Given action a_h at decision epoch k, it is possible that even if we hire a driver at each decision epoch from k+1 through ρ(ρ ≥ k + 1), there are still |Θ_k|+|∪^ρ_{τ=k+1}D_τ|-D(I_k, a_hl_m∪(l_{m^†})_{m^†}∈M^†, ω_m∪ (ω_m^†)_{m^†}∈M^† ,Θ_k) units of orders unable to be scheduled at decision epoch ρ(ρ > k), where M^† is the set of drivers recruited from decision epochs k + 1 through ρ. Therefore, if |Θ_k| + | ∪^ρ_{τ=k+1} D_τ | − D(I_k, a_hl_m∪(l_{m^†})_{m^†}∈{M^†}, ω_m ∪ (ω_{m^†})_{m^†}∈M^† ,Θ_k)> 0, we need to hire driver m that arrives at decision epoch k for compensation. Let W_{kρ} represent the expected shortage of capacity at decision epoch ρ resulting from the recruitment decision made at decision epoch k. We have W_{kρ} =max{|Θ_k|−D(I_k, a_hl_m,ω_m,Θ_k), 0}, ρ= k W_{kρ}=E[max{|Θ_k|+|∪^ρ_{τ=k+1 }D_τ|-D(I_k, a_hl_m∪(l_{m^†})_{m^†}∈M^† ,ω_m ∪ (ω_{m^†})_{m^†}∈M^† ,Θ_k), 0}], ρ ≥ k +1 To avoid hiring too few drivers, we set a parameter c_d, which represents a per-order penalty for not hiring enough crowdsourced drivers and delivering orders at greater costs via third party drivers. Thus, given action ah taken at decision epoch k, we have a total penalty cost of c_dΣK_{ρ=k+1}W_{kρ} for decision epochs k+1 through ρ. Let c_p represent the per-order cost paid to the third party drivers for delivering orders at the end of the time horizon. Let L_k(a_h) represent the expected compensation costs associated with action ah at decision epoch k. Thus, we have L_k(a_h)= c_dΣK_{ρ=k+1}W_{kρ} +c_pW_{kK}. (2) In the marginal cost balancing heuristic, we take an action ah that minimizes the value of |H_k(a_h)−L_k(a_h)| at each decision epoch. We note that while H_k(a_h) and L_k(a_h) are expected costs, we use sample average approximation scheme to approximate the expected values of |H_k(a_h)−L_k(a_h)|.

After making the recruitment decisions, we employ an insertion heuristic to assign the unassigned orders to all the hired drivers and develop routes for the drivers. In the heuristic, new orders are inserted into an existing route in the way that the increment in the route length is minimized. We evaluate our policies in a rolling horizon scheme with a set of sample paths. We note that the performance of the marginal cost balancing heuristic may depend on the value of parameter c_d. In the computational experiments, we examine the impact of different values of cd. The details of the experiments are as follows.

3. Preliminary Results In the preliminary experiments, we consider an operation horizon of 8 hours. We assume that crowdsourced drivers arrive in the system according to a Poisson process, so does the customer orders. The arrival rates for the drivers and customer orders are 6 drivers per hour and 24 orders per hour, respectively. We assume that the salary paid to each hired crowdsourced driver is $18 per hour (c_h =18). We assume that it costs $15 to hire a third party driver to deliver the order at the end of the time horizon (c_p = 15). We consider three benchmark heuristics to compare with our marginal cost balancing heuristic discussed above. The first heuristic is not to hire any crowdsourced drivers

MCB Heuristic Heuristic 1 Heuristic 2 Heuristic 3 Value of c_d -0.7 n/a n/a 17.3 Objective 1243.69 2890.64 1736.97 2403.42 Gap - 132.4% 39.7% 93.2% Hired crowdsourced drivers 21.3 0 31.5 18.1 Costs for hiring crowdsourced driver 1203.37 0 1697.78 1145.32 Orders served by third party drivers 2.7 192.7 2.6 83.9 Costs for hiring third party drivers 40.32 2890.64 39.2 1258.1 Table 1 Preliminary Results

and let the third party drivers to deliver all the orders at the end of the horizon. The second heuristic is only hiring new drivers if the current hired drivers cannot serve all the unassigned orders. The third one is to choose an action at each decision epoch that minimizes Equation (3). C(S_k, a_k)= a_hc_hl_m +c_d max{|Θ_k|−D(I_k, a_hl_m,ω_m,Θ_k), 0} (3) The preliminary experiments are presented in Table 1. The second column of the table presents the results obtained by implementing the marginal cost balancing (MCB) heuristic to make driver recruitment decisions. The third through the fifth columns present the results obtained from the above three benchmark solutions. As shown in the table, our MCB based heuristic performs better than all the three benchmarks. We note that we have tried different values of c_d between -0.2 and 20. The value of cd for us to obtain the best objective with the MCB heuristic is -0.7, while that for us to obtain the best objective with Heuristic 3 is 17.3. We note that a negative value of c_d implies encouraging the system to postpone hiring crowdsourced drivers, while a positive value of c_d penalizes the system for not hiring drivers as earlier as possible.

4. Conclusion To the best of our knowledge, this work is the first to investigate a stochastic crowdsourced delivery problem in which drivers rent electric vehicles to deliver orders for an online retailer. We consider uncertainties in the arrival of crowdsourced drivers and customer orders, as well as the battery level of the electric vehicles. We propose a marginal cost balancing heuristic to make driver recruitment decisions and implement routing heuristic to develop routes for drivers. The preliminary results demonstrate the effectiveness of our solution approach. As the next step, we will investigate the existence of an good lower bound to evaluate our solution quality.

References Manthey N, 2020 Trend europe: Electrification in car-sharing fleets. Retrieved on October 18, 2022, https://www.electrive.com/2020/03/08/trend-europe-electrification-in-car-sharing-fleets/. Woods B, 2022 How the massive ev transition is starting in the car rental industry. Retrieved on Octorber 18, 2022, https://www.cnbc.com/2022/06/18/how-the-massive-ev-transition-is-starting-in-the-car-rental-industry.html.

ABSTRACT. Studies measuring the regularity of individual travel behavior over time and, more generally, the decision-making process of travelers, are fundamental for service providers to enhance customer analytics and demand prediction. Research on travelers’ commuting patterns usually rely on some sort of clustering technique for the identification of similar groups of trips and, often, trip purpose or location labels are used. However, with companies moving to hybrid work schedules and new ways of earning a living, defining commuting based solely on these features could potentially lead to less data available, misidentification of the most regular routes, and, ultimately, faulty results. We propose the investigation of commuting from the perspective of trips sharing similar characteristics and high frequency, hence allowing more flexibility in the choice of features as well as interpretability in the form of a statistical model. We use unlabeled GPS tracking data consisting of 2901 public transport trips of 172 users in the city of Zurich, Switzerland. First, we identify all the commuting trips based on spatial and temporal variables through a hierarchical clustering approach. Then, after finding the cluster of the most frequent trips (sharing similar spatiotemporal characteristics) for each user, we fit a tree-boosted mixed effects model to study which variables are relevant for the identification of commuting patterns. In general, our results agree with the state-of-the-art research on commuting behavior, indicating that long distances and times, especially transfer times, pull users away from commuting, whereas commuting is still mainly observed during peak hours and weekdays. However, by defining commuting in a broader sense, we can include all the similar trips that affect the user's life and the network in the same manner, an advantage compared to traditional methods, with increasing relevance as society moves towards more flexible work environments.

ABSTRACT. In this work, we present a proof-of-concept investigation of a new service system Autonomous Modular Public Transit (AMPT) at a network scale and compare it with the traditional fixed-route, fixed capacity transit service in terms of total cost – both capital and operational on the agency side and time cost on the passenger side, as well as energy cost – and load factor. We develop stylized design models for AMPT on a grid network in a range of demand density scenarios with both homogenous and heterogeneous distributions. The AMPT models explicitly account for pod joining and disjoining (and therefore enabled en-route transfers of passengers) and potential energy savings due to pod train formation (platooning), which represent major departures from the traditional transit models in the literature.

ABSTRACT. Predicting pedestrian flows in transportation areas is a major research topic that can be used to enrich passenger information for public transport passengers, who may thus better plan their trips. It can also be used by transport operators to regulate transport supply with regards to demand. Much of the work on user demand prediction focus on average predictions, and therefore cannot be used for uncertainty analysis. However, this uncertainty is particularly appropriate in the transportation domain, where the risk of poorly managed high demand is to be avoided. We propose the implementation of probabilistic prediction models of passenger flows in a major multimodal transportation hub with methods based on deep learning. These models are able to model uncertainty by relying on an abstraction of contextual data and by assuming output distributions. We implement a new probabilistic prediction model based on deep learning, adding to the literature associated with these models. Our model learns a latent representation of the input data with the help of a recurrent neural network, and then translates it into multi-point passenger flow predictions with a "sum and shares" distribution, encountered in the literature. We compare this model with others from the state of the art, using open source data and data on the La Défense hub case study. Our model seems to better perform in specific situations where data present regularities.

ABSTRACT. We propose a novel learning-based branching strategy in the branch-price-and-cut (BPC) framework for solving vehicle routing problems (VRPs), which successfully imitates strong branching (SB) when exact column generation is used for computing the SB scores. We introduce multiple new features that are essential for improving learning accuracy. Although obtaining the features requires additional computational effort, it pays off once the models are trained. Preliminary results show that our CVRP solver using the learned branching strategy reduces CPU time by around 40% and the number of nodes explored by up to 30% compared with the VRPSolver in \cite{Pessoa et al., 2020}. Although we have only tested CVRP instances, we believe the methodology can be easily transferred to other VRPs, such as VRPTW, which we are actively testing.

ABSTRACT. In this paper, we propose a method for learning drivers' preferences from routing examples. In particular, we focus on last mile routing problems, where drivers start from a depot, then visit a predefined set of customers and come back to the depot. We interpret these last mile routing examples as optimal solutions to Traveling Salesperson Problems (TSPs), computed by expert drivers using an unknown cost function. From this interpretation, we develop an Inverse Optimization approach to learn from expert human drivers. That is, given a dataset of historical routes, we use Inverse Optimization to learn the unknown cost function assumed to be used by the drivers to compute their routes. In particular, for last mile routing problems, learning this cost function translates to learning the routing preferences of the drivers. We test our method in the Amazon Last Mile Routing Research Challenge. For this challenge, Amazon.com, Inc. released a dataset of thousands of real-world routes from expert human drivers and challenged research to propose models that replicate the routing preferences of the drivers. Our final approach achieves a score that ranks 4th out of the 48 models that qualified for the final round of the challenge.

ABSTRACT. In 2021, the courier, express, and parcel (CEP) market has been valued at $407.7 billion worldwide, with an estimated annual growth of 6.3% (Allied Market Research 2022). Last mile delivery is responsible for 40-50% of total CEP distribution costs and is often unsuccessful; reports have shown that the first delivery attempt fails in up to 10% of deliveries, with an average cost of $17 per failure. An increasingly popular delivery option is the out-of-home (OOH) delivery, for which the parcel is delivered at staffed parcel delivery points or automated parcel lockers, after which the customer picks up the parcel. The number of offered OOH-points has shown a yearly increase of up to 36%. OOH-delivery can potentially save logistics companies in routing costs, reduce delivery failure, and improve customer satisfaction. In this paper, we consider dynamic decision of allocating OOH-points, i.e., selecting OOH-points to offer from the complete set, to newly arriving online customers and the possibility to influence customer behavior by providing discounts, i.e., dynamic selection and pricing. These are by no means trivial decisions: we need to anticipate future customer arrivals and opportunity costs when determining the selection and pricing decision. Our contribution to scientific literature is threefold: (i) we define the OOH selection and pricing problem by means of an MDP, (ii) we adapt and compare several solution methods from time slotting literature and compliment them with a machine learning based approach, and (iii) we conduct an extensive analysis of stylized and real problems, and provide new insights into the problem and solution methods. We use the publicly available data from Amazon from the greater Seattle area. Amazon offers OOH-points in Seattle as of June 2022.

ABSTRACT. This research is inspired by the desire of shippers to reduce the emissions associated with their logistics operations and carriers to achieve their own profitability and sustainability targets while satisfying shipper expectations regarding transportation services. While hydrogen fuel cell and battery-electric vehicles present opportunities to reduce emissions, effectively integrating their use into operations given range limitations, recharging (refueling) times, and limited battery charging and hydrogen infrastructure requires careful planning. Further, reducing emissions requires accurately estimating emissions from operations. Critical to this estimation is a recognition that the emissions associated with energy production can vary from one region to another. This is also true with respect to the price of both energy and diesel fuel. We propose the Service Network Design Problem with Fleet and Emissions Management (SND-FEM). This problem considers fleet management decisions regarding how many vehicles of each type (diesel, electric, hydrogen) a carrier should acquire as well as in what regions they should operate. The impact of these fleet-level decisions on customer service is captured by explicitly modeling the routing of shipments and vehicles while recognizing the consumption of limited onboard resources (electrical energy, diesel fuel, hydrogen). Like the scheduled service network design problem (SSNDP), the SND-FEM ensures that a set of commodities are transported from their respective origins to their respective destinations. To do so, it ensures sufficient tractor capacity is routed to transport those commodities. Each type of tractor (diesel, battery-electric, hydrogen-electric) runs on and can store a limited amount of a given resource. The range of a tractor is determined by its onboard resource storage capacity and consumption rate for that resource. The model ensures that the movements of a tractor adhere to the range limitation of its type. The SND-FEM models the replenishment of resources by a vehicle as occurring at service nodes. These nodes may or may not also be terminals in the network wherein shipments are loaded and/or unloaded from vehicles.

ABSTRACT. Given an existent network of warehouses, where the parcel is moved for same-day deliveries, an alternative service utilizing idle transit capacity is to be considered to reduce overall costs and truck trips within the city. The transit line has scheduled departures and a fixed capacity to carry freight demand in the same trip that carries passengers and it is available upon a fixed cost for utilizing the routes. The goal is to reduce the costs of the operation by integrating the transit lines into the existing network, and deciding which transit routes should be invested in this scenario. A service network design model is proposed for this problem, where route selection is incorporated into the model, as well as selecting which commodities to supply in this network. The model is formulated over a time-expanded network, ao an algorithm based on dynamic discretization discovery (DDD) is proposed to insert new time points into the network and reduce the size of the model. The algorithm also relies on clustering commodities together considering their similarities in time availability. Preliminary results for a small network are presented, reducing significantly the solving time for this model.

ABSTRACT. Please see the attachment.

ABSTRACT. The use of underground freight transportation systems (UFT), an unmanned system in which close-fitting capsules or trains of capsules carry freight through tubes between different locations, offers many beneficial features for last mile delivery, including a reduction in emissions and congestion on the road. But, building such a system requires a significant capital expense, so cities or companies must carefully consider how and where to build the tunnels or UFT network. We model the problem of designing a UFT network along an existing road network in an urban environment to maximize the demand served by UFT subject to a capital expense budget. We transform this problem into an existing NP-hard problem where known strong formulations exist and provide computational results on urban environments to help weigh the tradeoffs vs. potential impact.

ABSTRACT. In this work, we are interested in optimizing the passenger flow between the station platform and vehicles (trams, trains or buses) at a public transport station. We propose a Nonlinear Programming (NLP) model to minimize the maximum door opening time at stations required for all passengers to board or alight the vehicle. The time needed for passengers to board and alight a vehicle follows a non-linear function that depends on the capacity of the platform and vehicle, the density inside the vehicle and the platform density. Our study intends to shed light to practitioners on how to design and implement a passenger guidance system to minimize vehicle boarding and alighting times.

ABSTRACT. With the increasing demand for e-commerce and same-day delivery, freight movements in urban areas have increased fast, causing traffic congestion, air pollution, and greenhouse gas emissions. Microhub with automated locker or parcel stations has recently gained traction. On the other hand, crowdshipping is an emerging crowdsourcing-based delivery service to reduce truck traffic and emissions. In this study, we propose and demonstrate an urban delivery paradigm using microhubs in combination with crowdshipping (M+C for short). First, we mathematically formulate the M+C as a concurrent Many-to-Many Pickup-and-Delivery Problem with Split Loads (M2MPDPSL) for truck routing with a Mixed Pickup and Delivery Vehicle Routing Problem (MPDVRP) for crowdshipping. To solve a large-scale M+C service, we construct the Maximum Split-Benefit with the Tabu Search heuristic and another heuristic algorithm for truck routing coupled with the MOSEK solver for MPDVRP. We then investigate the M+C service characteristics against a set of key technical parameters, including service area size, number of customers (customer density), crowdshipper compensation, and late pickup penalty. We find that the M+C achieves greater cost efficiency than the traditional centralized hub-based delivery system with medium to higher customer density. We also show that the M+C significantly reduces the number of trucks dispatched and total vehicle miles traveled (VMT), thus consuming less fuel and emitting fewer air pollutants. Overall, it has greater flexibility and on-time performance than the traditional centralized hub-based delivery system.

ABSTRACT. The solution of the Multi-Depot Vehicle Scheduling Problem (MDVSP) can often be improved substantially by incorporating Trip Shifting (TS) as a model feature. By allowing departure times to deviate a few minutes from the original timetable, new combinations of trips may be carried out by the same vehicle, thus leading to more efficient scheduling. However, explicit modelling of each potential trip shift quickly causes the problem to get prohibitively large for current solvers, such that researchers and practitioners were obligated to resort to heuristic methods to solve large instances. In this paper, we develop a Dynamic Discretization Discovery algorithm that guarantees an optimal continuous-time solution to the MDVSP-TS without explicit consideration of all trip shifts. It does so by iteratively solving and refining the problem on a partially time-expanded network until the solution can be converted to a feasible vehicle schedule on the fully time-expanded network. Computational results demonstrate that this algorithm outperforms the explicit modelling approach by a wide margin and is able to solve the MDVSP-TS even when many departure time deviations are considered.

ABSTRACT. In the Multi-Depot Vehicle Routing Problem (MDVRP), the assignment of customers to depots decomposes the original problem into distinct Capacitated Vehicle Routing Problems (CVRPs). We propose a simplified genetic algorithm to improve customer-depot assignments by evaluating decompositions using a neural network. The deep learning model predicts the optimal solution cost for a CVRP problem corresponding to each depot. We use a CVRP solver at the final stage to obtain the routes and actual solution costs for the top-ranked individuals from the genetic algorithm. Our numerical experiments show that this simplified approach is effective in improving the solution quality with computational advantages.

ABSTRACT. Synchromodal transport is an advanced version of intermodal transport, which has the potential to provide low-cost, reliable, and sustainable services by utilizing multiple modes (such as road, railway, and inland waterway) in combination with real-time updates. To provide such services, one necessary task of synchromodal transport is to adapt to service time uncertainty and handle unexpected events at terminals (including ports and train/truck stations). Unexpected events, such as congestion and bad weather, may trigger long waiting time and infeasible transport plans, causing low efficiency, high cost, and request cancellation. The existing approaches in literature assume probability distributions of uncertainty are available before the action is taken and do not detect the changes in the current environment. However, the information about uncertainty is usually incrementally revealed during transportation and the planning performance may decline when the environment changes. In this paper, we propose an online Reinforcement Learning (RL) approach to take into account the service time uncertainty in synchromodal transport. The collected information from the digital platform can be used to learn the pattern of uncertainties by RL. By learning online, RL can handle the uncertainty and help the operators to take wiser decisions by choosing suitable services at the right time.

ABSTRACT. Transportation problems have become increasingly dynamic. Global interconnectedness, urbanization, ubiquitous real-time information streams, and stronger service-orientation induce the need for frequent re-optimization of complex combinatorial transportation problems to keep an edge in a competitive market. Examples span from simpler dynamic knapsack problems, such as dynamic freight selection, to more complex dynamic routing problems, such as same-day delivery. Notably, all these problems involve not only searching a combinatorial and constrained action-space for adequate actions, but also evaluating actions with respect to future stochastic dynamic developments. A solution to these dynamic transportation problems is a decision policy instead of a single solution vector. In theory, reinforcement learning (RL) is an ideal solution method for this problem class because (i) combinatorial transportation problems can naturally be modeled as sequential decision processes and (ii) learning architectures, such as neural networks, can be trained offline to return fast and complex decision policies. However, in dynamic transportation problems the decision policy must assign an action from the complex, combinatorial action space to each state of the system. Each action must typically satisfy the specific problem constraints such as capacity, time windows, and deadlines. RL methodology is challenged by such complex, combinatorial actions as it is more concerned with evaluating actions than searching complex action spaces. As such, the majority of available RL-techniques remains nearly untouched in past dynamic transportation problems. Instead, alternative strategies are applied, often based on the operations research community's well-known expertise using mixed-integer linear programming and focused more on efficiently finding an action given current information, often at the cost of neglecting future uncertainty. We aim to bridge this gap by proposing two promising approaches that combine reinforcement learning and mixed-integer linear programming to simultaneously search and evaluate complex, combinatorial action spaces of dynamic transportation problems. We implement and evaluate the proposed solution methods for a sequence of increasingly complex transportation problems to highlight the methods' individual advantages.

ABSTRACT. Current free and subscription-based trip planners have heavily focused on providing available transit options to improve the first and last-mile connectivity to the destination. However, those trip planners may not truly be multimodal to vulnerable road users (VRU)s since those selected side walk routes may not be accessible or feasible for people with disability. Depending on the level of availability of digital twin of travelers behaviors and sidewalk inventory, providing the personalized suggestion about the sidewalk with route features coupled with transit service reliability could be useful and happier transit riders may boost public transit demand/funding and reduce rush hour congestion. In this paper, the adaptive trip planner considers the real-time impact of environment changes on pedestrian route choice preferences (e.g., fatigue, weather conditions, unexpected construction, road congestion) and tolerance level in response to transit service uncertainty. Side walk inventory is integrated in directed hypergraph on the General Transit Feed Specification to specify traveler utilities as weights on the hyperedge. A realistic assessment of the effect of the user-defined preferences on a traveler’s path choice is presented for a section of the Boston transit network, with schedule data from the Massachusetts Bay Transportation Authority. Different maximum utility values are presented as a function of varying traveler’s risk-tolerance levels. In response to unprecedented climate change, poverty, and inflation, this new trip planner can be adopted by state agencies to boost their existing public transit demand without extra efforts

ABSTRACT. As extreme weather events become more frequent and disruptive, service restoration is increasingly important for many infrastructures, e.g., power grids and communication networks. In many studies on service restoration, the logistics issue of traveling over the road network, however, is often overlooked due to the complexity of considering multiple networks simultaneously, resulting in prolonged disruption time. In this work, we address such a problem arising in power systems, where technical crew and utility trucks travel to a number of sites to repair damaged equipment, with the goal of minimizing the total service disruption time within the service region. We call this problem the Power Restoration Traveling Repairman Problem (PRTRP). What makes it significantly more challenging than a typical routing problem is that the service disruption time in a location depends on the interaction of the routing sequence with both networks, i.e., the road network and the power grid. To solve the problem, we develop an exact method based on bi-directional dynamic programming. We then improve the method by reducing the search space with solution upper and lower bounds, and threshold rules derived from the precedence relations in the power network. We also propose efficient heuristic variants of the method. We present computational results and compare our method with benchmark heuristics.

ABSTRACT. The sustainability of urban logistics could be improved by a partial transition of urban freight delivery from ground-based vans and light commercial vehicles to cargo bikes and Uncrewed Aerial Vehicles (UAVs). Due to the benefits of UAVs in terms of transit speed, reduced emissions, and improved access to remote/rural areas, the healthcare sector could particularly benefit from the use of drones, as many medical products could have short shelf lives and therefore require a timely collection/delivery. The Drone Medical Logistics project, which is part of the Solent Future Transport Zone (FTZ) programme funded by the UK Department for Transport (DfT), focuses on developing a simulation environment for optimising and evaluating multi-modal supply chains involving land-to-UAV and UAV-to-land logistics interchanges. This study aims to develop multi-modal logistics planning and optimisation tools that will enable a fleet manager to quantify in what ways drones can be used as part of integrated fleets to efficiently improve deliveries/collections of medical/healthcare products between hospitals and surgeries in the Solent region, whilst reducing emissions and mean receipt times at the pathology labs to improve patient care.

ABSTRACT. This paper proposes a curb-aware network modeling framework that encapsulates the route choice, competition, and interactive effect among different curb users simultaneously and embeds the dynamics of curb usage and the associated network impact into the mesoscopic DNL model.The proposed DTA framework models the travelers’ choice behaviors related to curb usage. A multi-modal dynamic user equilibrium model (DUE) is formulated among three modes: private driving, ride-hailing, and commercial trucks. We model the choices of parking locations for driving, curb PU/DO locations for ride-hailing, and curb loading/unloading locations for commercial trucks simultaneously. Curbside pricing and space restrictions are also embedded in the generalized cost of different modes. It offers a holistic approach to assess how travelers’ choices will be changed and how system-level performance will be impacted when curbside management strategies are implemented. It refines curb space searching and usage dynamics are integrated into the mesoscopic DNL model for estimating dynamic traffic conditions (i.e. travel time). Real-world curb usage data is used to calibrate the proposed framework together with other multi-source traffic sensor data.

ABSTRACT. Truck platooning requires coordination to be successful. Multiple aspects involved in truck platoon coordination, including willingness-to-platoon, routing choices, platooning options, and interactions with surrounding traffic are rarely considered simultaneously. This study proposes a unified model framework for examining spontaneous truck-platooning coordination, taking into consideration their willingness-to-platoon, the time cost in the platoon formation process, and the interdependence with the background traffic, including both individual trucks and `non-platoonable' passenger vehicles. Unlike other relevant studies that take the centralized optimization approach, the present study establishes a static multi-class traffic assignment model framework using the user equilibrium principle. Interdependence complexes are treated through network reconstruction, link performance function generalization, and reconciliation of dynamic processes with stochastic stationary traffic flows. A stochastic variational inequality is constructed to delineate the equilibrium conditions, which can then be solved using standard algorithms.

ABSTRACT. System optimum (SO) routing, wherein the total travel time of all users is minimized, is a holy grail for transportation authorities. However, SO routing may discriminate against users who incur much larger travel times than others to achieve high system efficiency, i.e., low total travel times. To address the inherent unfairness of SO routing, we study the $\beta$-fair SO problem whose goal is to minimize the total travel time while guaranteeing a $\beta\geq 1$ level of unfairness, which specifies the maximum possible ratio between the travel times of different users with shared origins and destinations.

To obtain feasible solutions to the $\beta$-fair SO problem while achieving high system efficiency, we develop a new convex program, the Interpolated Traffic Assignment Problem (I-TAP), which interpolates between a fair and an efficient traffic-assignment objective. We evaluate the efficacy of I-TAP through theoretical bounds on the total system travel time and level of unfairness in terms of its interpolation parameter, as well as present a numerical comparison between I-TAP and a state-of-the-art algorithm on a range of transportation networks. The numerical results indicate that our approach is faster by several orders of magnitude as compared to the benchmark algorithm, while achieving higher system efficiency for most levels of unfairness. We further leverage the structure of I-TAP to develop two pricing mechanisms to collectively enforce the I-TAP solution in the presence of selfish homogeneous and heterogeneous users, respectively, that independently choose routes to minimize their own travel costs. We mention that this is the first study of pricing in the context of fair routing for general road networks (as opposed to, e.g., parallel road networks).

ABSTRACT. The System Optimal Dynamic Traffic Assignment (SO-DTA) aims to solve the time-dependent traffic flow within minimum travel cost given an Origin-Destination (OD) demand in a road network. Existing studies mainly focus on the link-based SO-DTA model in general networks, which can provide fine-grained solutions. However, in real-world applications, it is practically infeasible to estimate the fundamental diagram on each road due to the installation and maintenance expense of sensors. Therefore, such solutions may not be reliable as the traffic dynamics may be biased from those in the real world. The macroscopic region-based models enable the aggregate modeling of local roads, which could relax the information required for each road. Although the SO-DTA solution should be coarse-grained, it is more reliable as it is prone to calibrate a single Macroscopic Fundamental Diagram (MFD) for a region. To trade-off between granularity and reliability when solving the SO-DTA problem, in this paper, we propose a hybrid modeling of road networks, which simultaneously uses the link- and region-based models. The road network can be mainly separated into two parts, highways and local roads. The traffic dynamics on highways are modeled by the double queue model, while the traffic dynamics on local roads are modeled by the accumulation-based model. Furthermore, to ensure the convergence of SO-DTA solutions in large-scale and real-world networks, we linearize the accumulation-based model through a linear piecewise MFD and formulate a linear programming model for the SO-DTA problem in the hybrid road network. To demonstrate the accessibility of the SO-DTA in general networks, two numerical studies on a synthetic network and a real-world network in Hong Kong have been or will be developed.

ABSTRACT. Crowdsourced delivery, where occasional drivers make deliveries in exchange for some compensation, is a recent innovation in last-mile delivery. Along with its potential benefits, it also presents significant challenges since the acceptance behavior and the availability of occasional driver is often uncertain. The relation between compensation offered to occasional drivers and the probability that they are willing to perform a task has been mostly neglected in the scientific literature. Hence, we consider a setting in which compensation-dependent acceptance probabilities are explicitly considered in the process of assigning delivery tasks to occasional drivers. We propose a mixed-integer nonlinear program minimizing the total expected delivery cost under this setting. We show two probability functions modeling the driver behavior and derive an efficient two-stage solution approach that solves the considered problem in polynomial time for the considered probability functions. Finally, a computational study comparing our approach to existing ones shows the potential savings that can be obtained by integrating compensation decisions with the acceptance behavior in task assignments.

ABSTRACT. Crowd-shipping is a last-mile delivery concept in which commuters pick up and deliver parcels on their pre-existing paths. In urban areas, crowd-shipping circumvents problems that traditional last-mile delivery suffers from, such as road congestion and lack of parking spaces, especially if more sustainable modes of transport are utilized, like bikes or e-bikes. Thereby, it is more sustainable and less costly. Using transfers between crowd-shippers allows to expand the service area and improve the overall performance. However, as this requires synchronization over space and time, this makes the problem more complex. In this work, we develop a model that can encompass fully heterogeneous crowd-shippers and parcels. Thereby, it allows for both direct time-synchronized transfers as well as intermediate storage at designated parcel lockers. We design a column generation algorithm that allows to solve large-scale realistic instances to optimality. We evaluate the performance of our algorithm as well as the potential of crowd-shipping with transfers on a realistic case study of a bike-based crowd-shipping system in Washington DC.

ABSTRACT. This research proposes the use of heatmaps as a control lever to manage the probabilistic repositioning of independent drivers in crowdsourced delivery platforms. The platform aims to maximize order fulfillment by dynamically matching drivers and orders, and selecting heatmaps that trigger the probabilistic flow of unmatched drivers, so as to balance driver supply and delivery requests over the service region. We develop a Markov Decision Process (MDP) model to sequentially select matching and heatmap decisions, where the repositioning behavior of independent drivers is captured by a multinomial logit discrete choice model. The MDP model is solved using a rolling-horizon-based stochastic look-ahead policy, which decomposes matching and heatmap decisions into two optimization problems: a two-stage stochastic programming upper-bounding problem for matching decisions, and a mixed-integer programming problem for heatmap decisions. We also propose a simple policy for efficiently solving large-scale problems. An extensive computational study on instances derived from the Chicago ridehailing dataset is conducted. Computational experiments demonstrate the value of heatmaps in improving order fulfillment, beyond the level achieved by matching alone (up to 25%), and identify conditions that affect the benefit of using heatmaps to guide the repositioning of drivers.

ABSTRACT. Traffic systems exhibit supply-side uncertainty which is alleviated through real-time information. This article explores subscription models for a private agency sharing data at a fixed rate. A multiclass strategy-based equilibrium model is developed for two classes of subscribed and unsubscribed travelers, whose optimal strategy given the link-state costs is modeled as a Markov decision process (MDP) and a partially-observable MDP, respectively. A utility-based subscription choice model is formulated to study the impacts of subscription rates on the percentage of travelers choosing to subscribe. Solutions to the fixed-point formulation are determined using iterative algorithms. The proposed subscription model can be used for designing optimal subscription rates in various settings where real-time information can be a valuable routing tool such as express lanes, parking systems, roadside delivery, and routing of vulnerable road users.

ABSTRACT. The evolution of e-commerce has led to the emergence of new business models in last-mile delivery, especially regarding applications that require online tour planning. In same-day delivery (SDD), e.g., customers log in to an e-commerce platform, place an order, and expect its delivery within a few hours. This comes along with very high customer expectations regarding delivery speed. Consequently, in order to still operate profitably, managing last-mile delivery has evolved from optimizing fulfillment operations alone to, additionally, steering demand, i.e., integrated demand management and vehicle routing problems (i-DMVRPs) have emerged.The accompanying high practical relevance of i-DMVRPs with an online tour planning component, has prompted the progression of the research of stochastic dynamic vehicle routing problems toward integrating ideas from traditional revenue management literature.However, to the best of our knowledge, there exists no research that structurally analyses the application of choice-based linear programming (LP) models to solve online i-DMVRPs. Since choice-based LP models have proved to be very valuable in traditional demand management control mechanisms, we aim at closing this research gap: We introduce a concept of how to integrate choice-based demand management into an LP approach for online vehicle routing, in which both the vehicle routing as well as the demand control are optimized simultaneously. Thereby, we focus on an SDD problem in which an e-retail provider offers different delivery options for ordered goods to sequentially incoming customers, who then choose stochastically, according to their choice preferences. However, it is straightforward to transfer the concept to other i-DVMRPs.

ABSTRACT. Unmanned aerial vehicles are an integral part of any smart city vision. Multiple challenges, however, have to be addressed before an efficient utilization of this technology. One of the key challenges in this regard is the problem of collision-free multi-UAV routing and path planning in congested 3D networks. An effective solution to this problem requires addressing often contradicting objectives, including meeting the time requirements, ensuring safety, and increasing the flight time. Unfortunately, multi-UAV routing and path planning is an NP-hard problem and traditional approaches rely on heuristic methods to find near-optimal solutions, a challenge that can be addressed by quantum computers. The ongoing evolution of quantum computing hardware and the recent advances in quantum algorithms for mathematical programming make the routing and path planning problem of UAVs an avenue of research worthwhile to be explored on quantum devices. Accordingly, the main contribution of this paper is to introduce quantum algorithms for solving the collision-free multi-UAV routing problem in complex 3D transportation networks. Two algorithms will be proposed for a quantum annealing-based system and a quantum gate-base system and a comparison of these methods will be provided.

ABSTRACT. This work creates a general framework for characterizing how traffic dynamics in urban networks evolve with shifting mode and departure time choices. Starting with N-agent day-to-day departure time choices in a generalized bathtub model, the generalized mean-field game formulation facilitate the design of RL algorithms and reduces the complexity of the convergence analysis. We design a Mean-Field-Learning Policy-Gradient algorithm that converges to a stable dynamic network equilibrium solution asymptotically with the number of days.

ABSTRACT. In transportation networks, road tolling schemes are a method to cope with the efficiency losses due to selfish user routing, wherein users choose routes to minimize individual travel costs. However, the efficacy of tolling schemes often relies on access to complete information on users' trip attributes, such as their origin-destination (O-D) travel information and their values of time, which may not be available in practice.

Motivated by this practical consideration, we propose an online learning approach to set tolls in a traffic network to drive heterogeneous users with different values of time toward a system-efficient traffic pattern. In particular, we develop a simple yet effective algorithm that adjusts tolls at each time period solely based on the observed aggregate flows on the roads of the network without relying on any additional trip attributes of users, thereby preserving user privacy. In the setting where the O-D pairs and values of time of users are drawn i.i.d. at each period, we show that our approach obtains an expected regret and road capacity violation of $O(\sqrt{T})$, where $T$ is the number of periods over which tolls are updated. Our regret guarantee is relative to an offline oracle with complete information on users' trip attributes. We further establish a $\Omega(\sqrt{T})$ lower bound on the regret of any algorithm, which establishes that our algorithm is optimal up to constants. Finally, we demonstrate the superior performance of our approach relative to several benchmarks on a real-world traffic network, which highlights its practical applicability.

ABSTRACT. Estimating multimodal distributions of travel times (TT) from real-world data is critical for understanding and managing congestion. Mixture models can estimate the overall distribution when distinct peaks exist in the probability density function, but no transfer of mixture information under epistemic uncertainty across different spatiotemporal scales has been considered for capturing unobserved heterogeneity. In this paper, a physics-informed and -regularized (PIR) prediction model is developed that shares observations across similarly distributed network segments over time and space. By grouping similar mixture models, the model uses a particular sample distribution at distant non-contiguous unexplored locations and improves TT prediction. The model includes hierarchical Kalman filtering (KF) updates using the traffic fundamental diagram to regulate any spurious correlation and estimates the mixture of TT distributions from observations at the current location and time sampled from the multimodal and multivariate TT distributions at other locations and times. In order to overcome the limitations of KF, this study developed dynamic graph neural network (GCN) model which uses time evolving spatial correlations. The KF model with PIR predicts traffic state with 19% more accuracy than TMML model in Park et al.(2022) and GCN model will further reduce the uncertainty in prediction. This study uses information gain from explored correlated links to obtain accurate predictions for unexplored ones.

ABSTRACT. Scheduled service network design (SSND) problems are key issues in tactical transport planning. However, while transport systems are inherently subject to many sources of uncertainty, most of the SSND-related literature mainly focuses on deterministic variants. The literature on Stochastic Scheduled Network Design Problem (SSNDP) typically presumes that the carrier determines both the network and the schedule before having complete visibility of shipment volumes. This assumption is appropriate for settings where the carrier must commit to a schedule either to its internal operational team or to external providers, e.g. scheduled ships/airplanes in maritime/air transportation. But in the case of more flexible modes such as trucking, the scheduling of the services can be delayed until after volumes are revealed, potentially enabling greater consolidations and lower costs. Here, we investigate the value of modeling flexibility offered by transportation modes such as trucking and we derive managerial insights into how to manage a transportation system when flexibility is an option. We focus on a case where the carrier has to commit to the physical network before knowing shipment volumes. Recourse decisions determine (i) the timing of the operations while matching the physical paths and point-to-point services set in the first stage as well as (ii) the potential use of extra ad-hoc capacity. We introduce a formulation of the Stochastic Scheduled Service Network Design with Flexible Schedules (SSSNDFS). Through computational experiments, we observe that modeling flexible schedules generate significant savings, particularly for large instances. A qualitative comparison reveals that the flexible solutions are more cost-effective because they either (i) commit to more service capacity, enabling to reduce significantly the scenario subproblem costs, or (ii) commit to less service capacity. We also observe that modeling flexible schedules result in structurally different solutions in terms of physical network design.

ABSTRACT. In this study, we present the first robust optimization solution method for the continuous-time service network design problem (CTSNDP) under travel time uncertainty. We first propose a new compact deterministic model for the CTSNDP. Based on it, we then derive a two-stage robust optimization model with travel time uncertainty incorporated. To solve this robust optimization model, we develop a column-and-constraint generation (C&CG) algorithm, and then enhance it by applying some novel optimization techniques that adjust model parameters dynamically. The effectiveness and efficiency of our newly developed solution method have been demonstrated by extensive computational experiments.

ABSTRACT. A critical service network design challenge for package carriers are the so-called load planning problems. Load planning refers to decisions about how many trailer or container loads (perhaps of different types) to plan for dispatch over time between pairs of terminals. Such planned loads are the transportation capacity of the network. Another key component to the consolidation transportation plan are the decisions regarding which package volumes to assign into planned loads. This work considers dynamic optimization of load plans given fixed primary and alternate flow planning decisions. Network-wide simultaneous optimization of load planning adjustments is a daunting challenge due to the scale of the network; our partner operates more than 1200 terminals across the United States with an average daily shipment volume of more than 10 million packages. We develop local optimization models, one for each terminal over some short time horizon, with the goal of automating, and ideally improving, the decision-making process of current company load planners. The local optimization models report an average of 10-15% improvement in capacity utilization at the respective terminals. We leverage machine learning to develop optimization proxies which can be used to recurrently modify load plans, as new volume data is realized, in milliseconds. This methodology can assist planners in real-time, to effectively modify the base load plans, at a larger set of buildings than is currently possible, given the labor requirement.

ABSTRACT. Due to the growth of the e-commerce market and the increased expectation of quicker delivery time, performing last-mile delivery in highly populated areas is becoming more and more challenging. To deal with the increased volume and the shorter service time, a company usually operates the last-mile delivery on a two-echelon network. Our work focuses on the first echelon, where goods are distributed from a single distribution center (DC) or fulfillment center (FC) to multiple satellite hubs spread around the city. From a tactical planning perspective, we propose a rate-based vehicle routing problem (VRP) that considers the expected service time of each package when solving the fleet assignment and routing problems. The problem is formulated as a route-based model and solved with column generation. While the exact optimal solution is difficult to achieve within a reasonable time limit, we propose a heuristic approach based on the root-node solution achieved from the branch-and-bound tree. We evaluate the approach by solving a set of randomly generated instances, showing that our heuristics can efficiently solve the problem, providing a close-to-optimal solution using a shorter running time than the exact approach.

ABSTRACT. The technician park-and-loop routing problem is a variation of the vehicle routing problem in which routes include a main tour that is completed using a vehicle and subtours that are carried out on foot after parking the vehicle. Additionally, routes duration and total walking distance are bounded. To solve the problem, we propose a branch-price-and-cut algorithm as an exact solution methodology using problem-specific enhancements in the pricing scheme. We illustrate the effectiveness of our method on a set of instances with up to 50 customers in which the method compares favorably to existing metaheuristic algorithms matching all previously best-known solutions and improving 11 of them in reasonable computational times. Moreover, 38/40 instances are solved to optimality using the proposed branch-price-and-cut algorithm.

ABSTRACT. Routing vehicles and communicating estimated time windows to customers is a fundamental challenge. In this paper, we present a new solution approach for finding optimal time window assignments and vehicle routes. Our approach, named Scenario Clustered Benders Dual Decomposition, combines the latest advances in Benders decomposition and scenario clustering techniques. We demonstrate the effectiveness of our algorithm on the Time Window Assignment Traveling Salesperson Problem with stochastic travel times, showing improved performance over state-of-the-art techniques in terms of both lower and upper bounds. Our methodology also provides significant benefits in terms of computational efficiency.

ABSTRACT. n/a

ABSTRACT. Many policies and reforms implemented for city freight logistics are designed to cater to the needs of an urban population. Often, freight policies like establishing urban consolidation centers (UCC) in large urban cities may not be effective in smaller cities. Small city logistics have its own inherent features that make freight control policies of big cities inadequate. The main challenge in small city freight is the demand segmentation and limited transportation infrastructures. Smaller cities have low demand volume compared with larger cities. Our study focuses on evaluating the possibilities of Micro consolidation centers (MCC) with cross-docking favoring greener cargo bike distribution in small city freight logistics. We observe the role of zonal restriction policies on freight vehicles in promoting cargo bike distribution schemes. Specifically, we consider the case of the city of Bergen in their implementation of restriction zones and study the possibilities of MCCs with cross-docking using cargo bike delivery. Through building different routing models, we evaluated the options of UCC and MCC in the freight distribution in Bergen city. We observed higher capacity utilization in the case of MCC as cargo bikes with smaller capacities cater to the frequent low volume throughput from the MCC. Shorter trips with more frequency make cargo bikes ideal for small city logistics. The size advantages of cargo bikes transiting through narrow roads and requiring less parking space favor small city logistics.

ABSTRACT. Underground passageways for the transport of goods and people have fascinated mankind throughout the centuries. Recent initiatives in different parts of the world aim at rekindling the freight tunnel concept for urban logistics. According to this concept, freight is lifted into a tunnel, moved via electrically-powered vehicles, rail cars, or maglev shuttles toward inner-city micro hubs, and finally delivered with environmentally-friendly vehicles to urban recipients. The main justification for this concept to outweigh the huge tunnel boring cost is a substantial reduction of road-based urban freight traffic. To warn about unfulfilled expectations, however, we show that the combination of time-critical goods, small inner-city hubs with restricted storage capacity, and the wrong booking procedure can hinder a loading of tunnel vehicles to capacity. To do so, we consider a polynomially solvable scheduling problem where due date-restricted shipments are to be assigned to tunnel vehicles and delivered to a given set of micro hubs with limited storage capacity. Scarce hub capacities, tight due dates, and the wrong booking policy is shwon to lead to situations where up 80% of the tunnel capacity remain unused.