An efficient heuristic for the Multi-vehicle One-to-one Pickup and Delivery Problem with Split Loads

In this study, we consider the Multi-vehicle One-to-one Pickup and Delivery Problem with Split Loads (MPDPSL). This problem is a generalization of the one-to-one Pickup and Delivery Problem (PDP) where each load can be served by multiple vehicles as well as multiple stops by the same vehicle. In practice, split deliveries is a viable option in many settings where the load can be physically split, such as courier services of third party logistics operators. We propose an efficient heuristic that combines the strengths of Tabu Search and Simulated Annealing for the solution of the MPDPSL. Results from experiments on two problem sets in the literature indicate that the heuristic is capable of producing good quality solutions in reasonable time. The experiments also demonstrate that up to 33% savings can be obtained by allowing split loads; however, the magnitude of savings is dependent largely on the spatial distribution of the pickup and delivery locations.     

Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots

Dial-a-ride problems are concerned with the design of efficient vehicle routes for transporting individual persons from specific origin to specific destination locations. In real-life this operational planning problem is often complicated by several factors. Users may have special requirements (e.g. to be transported in a wheelchair) while service providers operate a heterogeneous fleet of vehicles from multiple depots in their service area. In this paper, a general dial-a-ride problem in which these three real-life aspects may simultaneously be taken into account is introduced: the Multi-Depot Heterogeneous Dial-A-Ride Problem (MD-H-DARP). Both a three- and two-index formulation are discussed. A branch-and-cut algorithm for the standard dial-a-ride problem is adapted to exactly solve small problem instances of the MD-H-DARP. To be able to solve larger problem instances, a new deterministic annealing meta-heuristic is proposed. Extensive numerical experiments are presented on different sets of benchmark instances for the homogeneous and the heterogeneous single depot dial-a-ride problem. Instances for the MD-H-DARP are introduced as well. The branch-and-cut algorithm provides considerably better results than an existing algorithm which uses a less compact formulation. All seven previously unsolved benchmark instances for the heterogeneous dial-a-ride problem could be solved to optimality within a matter of seconds. While computation times of the exact algorithm increase drastically with problem size, the proposed meta-heuristic algorithm provides near-optimal solutions within limited computation time for all instances. Several best known solutions for unsolved instances are improved and the algorithm clearly outperforms current state-of-the-art heuristics for the homogeneous and heterogeneous dial-a-ride problem, both in terms of solution quality and computation time.     

The time-dependent pollution-routing problem

The Time-Dependent Pollution-Routing Problem (TDPRP) consists of routing a fleet of vehicles in order to serve a set of customers and determining the speeds on each leg of the routes. The cost function includes emissions and driver costs, taking into account traffic congestion which, at peak periods, significantly restricts vehicle speeds and increases emissions. We describe an integer linear programming formulation of the TDPRP and provide illustrative examples to motivate the problem and give insights about the tradeoffs it involves. We also provide an analytical characterization of the optimal solutions for a single-arc version of the problem, identifying conditions under which it is optimal to wait idly at certain locations in order to avoid congestion and to reduce the cost of emissions. Building on these analytical results we describe a novel departure time and speed optimization algorithm for the cases when the route is fixed. Finally, using benchmark instances, we present results on the computational performance of the proposed formulation and on the speed optimization procedure.     

Use of vehicle signature analysis and lexicographic optimization for vehicle reidentification on freeways

The vehicle reidentification problem is the task of matching a vehicle detected at one location with the same vehicle detected at another location from a feasible set of candidate vehicles detected at the other location. This paper formulates and solves the vehicle reidentification problem as a lexicographic optimization problem. Lexicographic optimization is a preemptive multi-objective formulation, and this lexicographic optimization formulation combines lexicographic goal programming, classification, and Bayesian analysis techniques. The solution of the vehicle reidentification problem has the potential to yield reliable section measures such as travel times and densities, and enables the measurement of partial dynamic origin/destination demands. Implementation of this approach using conventional surveillance infrastructure permits the development of new algorithms for ATMIS (Advanced Transportation Management and Information Systems). Freeway inductive loop data from SR-24 in Lafayette, California, demonstrates that robust results can be obtained under different traffic flow conditions.     

The Pollution-Routing Problem

The amount of pollution emitted by a vehicle depends on its load and speed, among other factors. This paper presents the Pollution-Routing Problem (PRP), an extension of the classical Vehicle Routing Problem (VRP) with a broader and more comprehensive objective function that accounts not just for the travel distance, but also for the amount of greenhouse emissions, fuel, travel times and their costs. Mathematical models are described for the PRP with or without time windows and computational experiments are performed on realistic instances. The paper sheds light on the tradeoffs between various parameters such as vehicle load, speed and total cost, and offers insight on economies of ‘environmental-friendly’ vehicle routing. The results suggest that, contrary to the VRP, the PRP is significantly more difficult to solve to optimality but has the potential of yielding savings in total cost.     

Time-dependent green vehicle routing problem with stochastic vehicle speeds: An approximate dynamic programming algorithm

This paper addresses a Time Dependent Capacitated Vehicle Routing Problem with stochastic vehicle speeds and environmental concerns. The problem has been formulated as a Markovian Decision Process. As distinct from the traditional attempts on the problem, while estimating the amount of fuel consumption and emissions, the model takes time-dependency and stochasticity of the vehicle speeds into account. The Time Dependent Capacitated Vehicle Routing Problem is known to be NP-Hard for even deterministic settings. Incorporating uncertainty to the problem increases complexity, which renders classical optimization methods infeasible. Therefore, we propose an Approximate Dynamic Programming based heuristic as a decision aid tool for the problem. The proposed Markovian Decision Model and Approximate Dynamic Programming based heuristic are flexible in terms that more environmentally friendly solutions can be obtained by changing the objective function from cost minimization to emissions minimization. The added values of the proposed decision support tools have been shown through computational analyses on several instances. The computational analyses show that incorporating vehicle speed stochasticity into decision support models has potential to improve the performance of resulting routes in terms of travel duration, emissions and travel cost. In addition, the proposed heuristic provides promising results within relatively short computation times.     

A warehouse location-routing problem

The interdependence between distribution center location and vehicle routing has been recognized by both academics and practitioners. However, only few attempts have been made to incorporate routing in location analysis. This paper defines the Warehouse Location-Routing Problem (WLRP) as one of simultaneously solving the DC location and vehicle routing problems. We present a mixed integer programming formulation of the WLRP. Based on this formulation, it can be seen that the WLRP is a generalization of well-known and difficult location and routing problems, such as the Location-Allocation Problem and the Multi-depot Vehicle Dispatch Problem. It is therefore a large and complex problem which cannot be solved using existing mixed-integer programming techniques. We present a heuristic solution method for the WLRP, based on decomposing the problem into three subproblems. The proposed method solves the subproblems in a sequential manner while accounting for the dependence between them. We discuss a large-scale application of the proposed method to a national distribution company at a regional level.     

Estimation of mean and covariance of stochastic multi-class OD demands from classified traffic counts

This paper proposes a new model to estimate the mean and covariance of stochastic multi-class (multiple vehicle classes) origin–destination (OD) demands from hourly classified traffic counts throughout the whole year. It is usually assumed in the conventional OD demand estimation models that the OD demand by vehicle class is deterministic. Little attention is given on the estimation of the statistical properties of stochastic OD demands as well as their covariance between different vehicle classes. Also, the interactions between different vehicle classes in OD demand are ignored such as the change of modes between private car and taxi during a particular hourly period over the year. To fill these two gaps, the mean and covariance matrix of stochastic multi-class OD demands for the same hourly period over the year are simultaneously estimated by a modified lasso (least absolute shrinkage and selection operator) method. The estimated covariance matrix of stochastic multi-class OD demands can be used to capture the statistical dependency of traffic demands between different vehicle classes. In this paper, the proposed model is formulated as a non-linear constrained optimization problem. An exterior penalty algorithm is adapted to solve the proposed model. Numerical examples are presented to illustrate the applications of the proposed model together with some insightful findings on the importance of covariance of OD demand between difference vehicle classes.     

A bi-objective cyclist route choice model

It is widely acknowledged that cyclists choose their route differently to drivers of private vehicles. The route choice decision of commuter drivers is often modelled with one objective, to reduce their generalised travel cost, which is a monetary value representing the combined travel time and vehicle operating cost. Commuter cyclists, on the other hand, usually have multiple incommensurable objectives when choosing their route: the travel time and the suitability of a route. By suitability we mean non-subjective factors that characterise the suitability of a route for cycling, including safety, traffic volumes, traffic speeds, presence of bicycle lanes, whether the terrain is flat or hilly, etc. While these incommensurable objectives are difficult to be combined into a single objective, it is also important to take into account that each individual cyclist may prioritise differently between travel time and suitability when they choose a route.This paper proposes a novel model to determine the route choice set of commuter cyclists by formulating a bi-objective routing problem. The two objectives considered are travel time and suitability of a route for cycling. Rather than determining a single route for a cyclist, we determine a choice set of optimal alternative routes (efficient routes) from which a cyclist may select one according to their personal preference depending on their perception of travel time versus other route choice criteria considered in the suitability index. This method is then implemented in a case study in Auckland, New Zealand.The study provides a starting point for the trip assignment of cyclists, and with further research, the bi-objective routing model developed can be applied to create a complete travel demand forecast model for cycle trips. We also suggest the application of the developed methodology as an algorithm in an interactive route finder to suggest efficient route choices at different levels of suitability to cyclists and potential cyclists.     

Determining vehicle dispatch frequency when shipping frequency differs among suppliers

Collecting is a way to consolidate freight that involves trucks picking up material from more than one supplier on each trip to a single destination. Earlier research resulted in a method that optimizes collecting vehicle dispatch frequency and that assumes that all suppliers are visited on each dispatch. This paper develops a method that determines the optimal dispatch frequency when large suppliers are visited more frequently than are small suppliers. This added flexibility allows the combined inventory and transportation costs of collecting to be reduced. The method is developed analytically and illustrated with an example.     

Diesel-engined vehicle nitric oxide and soot emissions during the European light-duty driving cycle using a transient mapping approach

An engine mapping-based methodology is developed to gain a first approximation of a vehicle’s performance and emissions during a light-duty cycle. The procedure is based on a steady-state experimental investigation of the engine with an appropriate vehicle drivetrain model applied so that the cycle vehicle speed data can be transformed into engine speed and torque. Correction analysis is then applied based on transient experimentation to account for the transient discrepancies during real driving. The developed algorithm is applied for the case of a diesel-engined vehicle running on the European light-duty cycle. A comparative analysis is performed for each section of the cycle revealing its individual transient characteristics.     

Impacts of built environment and emerging green technologies on daily transportation greenhouse gas emissions in Quebec cities: a disaggregate modeling approach

This paper aims to investigate the impact of the built environment (BE) and emerging transit and car technologies on household transport-related greenhouse gas emissions (GHGs) across three urban regions. Trip-level GHG emissions are first estimated by combining different data sources such as origin–destination (OD) surveys, vehicle fleet fuel consumption rates, and transit ridership data. BE indicators for the different urban regions are generated for each household and the impact of neighborhood typologies is derived based on these indicators. A traditional ordinary least square (OLS) regression approach is then used to investigate the direct association between the BE indicators, socio-demographics, and household GHGs. The effect of neighborhood typologies on GHGs is explored using both OLS and a simultaneous equation modeling approach. Once the best models are determined for each urban region, the potential impact of BE is determined through elasticities and compared with the impact of technological improvements. For this, various fuel efficiency scenarios are formulated and the reductions on household GHGs are determined. Once the potential impact of green transit and car technologies is determined, the results are compared to those related to BE initiatives. Among other results, it is found that BE attributes have a statistically significant effect on GHGs. However, the elasticities are very small, as reported in several previous studies. For instance, a 10 % increase in population density will result in 3.5, 1.5 and 1.4 % reduction in Montreal, Quebec and Sherbrooke, respectively. It is also important to highlight the significant variation of household GHGs among neighborhoods in the same city, variation which is much greater than among cities. In the short term, improvements on the private passenger vehicle fleet are expected to be much more significant than BE and green transit technologies. However, the combined effect of BE strategies and private-motor vehicle technological improvement would result in more significant GHGs reductions in the long term.     

Forecasting automobile demand using disaggregate choice models

This paper presents a simulation model of the American automobile market. The simulation model combines a disaggregate model of household automobile number and type choice with an econometric model of used vehicle scrappage and simple models of new car supply. For fixed vehicle designs, consumer and producer interactions determine new car sales, used car scrappage and consumer vehicle holdings. The model allows automobiles to be highly differentiated and consumers to be heterogeneous. Short-run equilibrium is defined as supply equal to demand for every vehicle type during each market period. The automobile stock then evolves slowly as new vehicles are added and old vehicles are removed during each period. An empirical application of the simulation model with 12 consumer groups and 131 vehicle types is used to forecast automobile holdings. A base case scenario is run for 1978–1984 and compared with the observed market behavior during this period. Several other simulations are then run comparing different gasoline price scenarios with the base case for 1984–1990.     

A multi-period optimization model for the deployment of public electric vehicle charging stations on network

A multi-period multipath refueling location model is developed to expand public electric vehicle (EV) charging network to dynamically satisfy origin–destination (O–D) trips with the growth of EV market. The model captures the dynamics in the topological structure of network and determines the cost-effective station rollout scheme on both spatial and temporal dimensions. The multi-period location problem is formulated as a mixed integer linear program and solved by a heuristic based on genetic algorithm. The model and heuristic are justified using the benchmark Sioux Falls road network and implemented in a case study of South Carolina. The results indicate that the charging station rollout scheme is subject to a number of major factors, including geographic distributions of cities, vehicle range, and deviation choice, and is sensitive to the types of charging station sites.     

The load-dependent vehicle routing problem and its pick-up and delivery extension

The present paper examines a Vehicle Routing Problem (VRP) of major practical importance which is referred to as the Load-Dependent VRP (LDVRP). LDVRP is applicable for transportation activities where the weight of the transported cargo accounts for a significant part of the vehicle gross weight. Contrary to the basic VRP which calls for the minimization of the distance travelled, the LDVRP objective is aimed at minimizing the total product of the distance travelled and the gross weight carried along this distance. Thus, it is capable of producing sensible routing plans which take into account the variation of the cargo weight along the vehicle trips. The LDVRP objective is closely related to the total energy requirements of the vehicle fleet, making it a credible alternative when the environmental aspects of transportation activities are examined and optimized. A novel LDVRP extension which considers simultaneous pick-up and delivery service is introduced, formulated and solved for the first time. To deal with large-scale instances of the examined problems, we propose a local-search algorithm. Towards an efficient implementation, the local-search algorithm employs a computational scheme which calculates the complex weighted-distance objective changes in constant time. Solution results are presented for both problems on a variety of well-known test cases demonstrating the effectiveness of the proposed solution approach. The structure of the obtained LDVRP and VRP solutions is compared in pursuit of interesting conclusions on the relative suitability of the two routing models, when the decision maker must deal with the weighted distance objective. In addition, results of a branch-and-cut procedure for small-scale instances of the LDVRP with simultaneous pick-ups and deliveries are reported. Finally, extensive computational experiments have been performed to explore the managerial implications of three key problem characteristics, namely the deviation of customer demands, the cargo to tare weight ratio, as well as the size of the available vehicle fleet.     

Exploring the issue of integrating logistics and traffic control in urban areas

This paper proposes an optimization framework for urban transportation networks’ (re-)design which explicitly takes into account the specific decision-making processes of ordinary users and logistic operators. Ordinary users are typically commuters whose travels consist of well-defined pairs of origin and destination points, while logistic operators make deliveries at multiple locations. Obviously, these two user classes have different objectives and scopes of action. These differences are seldom considered in traffic research since most models aggregate the flow demand in OD matrices and use assignment models to predict the response of all users as if the dynamics of their optimization processes were of the same nature. This work demonstrates that better results can be achieved if the particular features of each user class are included in the models. It potentially improves the estimation of the responses and allows managers to shape their control measures to address specific user needs.     

Routing and charging locations for electric vehicles for intercity trips

This study addresses two problems in the context of battery electric vehicles (EVs) for intercity trips: the EV routing problem and the EV optimal charging station location problem (CSLP). The paper shows that EV routing on the shortest path subject to range feasibility for one origin–destination (O–D) pair, called the shortest walk problem (SWP), as well as a stronger version of the problem – the p-stop limited SWP – can be reduced to solving the shortest path problem on an auxiliary network. The paper then addresses optimal CSLPs in which EVs are range feasible with and without p-stops. We formulate the models as mixed-integer multi-commodity flow problems on the same auxiliary network without path and relay pattern enumeration. Benders decomposition is used to propose an exact solution approach. Numerical experiments are conducted using the Indiana state network.     

A real-life Multi Depot Multi Period Vehicle Routing Problem with a Heterogeneous Fleet: Formulation and Adaptive Large Neighborhood Search based Matheuristic

In this paper, a new rich Vehicle Routing Problem that could arise in a real life context is introduced and formalized: the Multi Depot Multi Period Vehicle Routing Problem with a Heterogeneous Fleet. The goal of the problem is to minimize the total delivery cost. A heterogeneous fleet composed of vehicles with different capacity, characteristics (i.e. refrigerated vehicles) and hourly costs is considered. A limit on the maximum route duration is imposed. Unlike what happens in classical multi-depot VRP, not every customer may/will be served by all the vehicles or from all the depots. The planning horizon, as in most real life applications, consists of multiple periods, and the period in which each route is performed is a variable of the problem. The set of periods, within the time horizon, in which the delivery may be carried out is known for each customer. A Mixed Integer Programming (MIP) formulation for MDMPVRPHF is presented in this paper, and an Adaptive Large Neighborhood Search (ALNS) based Matheuristic approach is proposed, in which different destroy operators are defined. Computational results, pertaining to realistic instances, which show the effectiveness of the proposed method, are provided.     

The travel and environmental implications of shared autonomous vehicles,using agent-based model scenarios

Carsharing programs that operate as short-term vehicle rentals (often for one-way trips before ending the rental) like Car2Go and ZipCar have quickly expanded, with the number of US users doubling every 1–2 years over the past decade. Such programs seek to shift personal transportation choices from an owned asset to a service used on demand. The advent of autonomous or fully self-driving vehicles will address many current carsharing barriers, including users’ travel to access available vehicles.This work describes the design of an agent-based model for shared autonomous vehicle (SAV) operations, the results of many case-study applications using this model, and the estimated environmental benefits of such settings, versus conventional vehicle ownership and use. The model operates by generating trips throughout a grid-based urban area, with each trip assigned an origin, destination and departure time, to mimic realistic travel profiles. A preliminary model run estimates the SAV fleet size required to reasonably service all trips, also using a variety of vehicle relocation strategies that seek to minimize future traveler wait times. Next, the model is run over one-hundred days, with driverless vehicles ferrying travelers from one destination to the next. During each 5-min interval, some unused SAVs relocate, attempting to shorten wait times for next-period travelers.Case studies vary trip generation rates, trip distribution patterns, network congestion levels, service area size, vehicle relocation strategies, and fleet size. Preliminary results indicate that each SAV can replace around eleven conventional vehicles, but adds up to 10% more travel distance than comparable non-SAV trips, resulting in overall beneficial emissions impacts, once fleet-efficiency changes and embodied versus in-use emissions are assessed.     

Controlling road congestion via a low-complexity route reservation approach

This work introduces a novel route reservation architecture to manage road traffic within an urban area. The developed routing architecture decomposes the road infrastructure into slots in the spatial and temporal domains and for every vehicle, it makes the appropriate route reservations to avoid traffic congestion while minimizing the traveling time. Under this architecture, any road segment is admissible to be traversed only during time-slots when the accumulated reservations do not exceed its critical density. A road-side unit keeps track of all reservations which are subsequently used to solve the routing problem for each vehicle. Through this routing mechanism, vehicles can either be delayed at their origin or are routed through longer but non-congested routes such that their traveling time is minimized. In this work, the proposed architecture is presented and the resulting route reservation problem is mathematically formulated. Through a complexity analysis of the routing problem, it is shown that for certain cases, the problem reduces to an NP-complete problem. A heuristic solution to the problem is also proposed and is used to conduct realistic simulations across a particular region of the San Francisco area, demonstrating the promising gains of the proposed solution to alleviate traffic congestion.