The Hybrid Vehicle Routing Problem

In this paper the Hybrid Vehicle Routing Problem (HVRP) is introduced and formalized. This problem is an extension of the classical VRP in which vehicles can work both electrically and with traditional fuel. The vehicle may change propulsion mode at any point of time. The unitary travel cost is much lower for distances covered in the electric mode. An electric battery has a limited capacity and may be recharged at a recharging station (RS). A limited number of RS are available. Once a battery has been completely discharged, the vehicle automatically shifts to traditional fuel propulsion mode. Furthermore, a maximum route duration is imposed according to contracts regulations established with the driver. In this paper, a Mixed Integer Linear Programming formulation is presented and a Large Neighborhood Search based Matheuristic is proposed. The algorithm starts from a feasible solution and consists into destroying, at each iteration, a small number of routes, letting unvaried the other ones, and reconstructing a new feasible solution running the model on only the subset of customers involved in the destroyed routes. This procedure allows to completely explore a large neighborhood within very short computational time. Computational tests that show the performance of the matheuristic are presented. The method has also been tested on a simplified version of the HVRP already presented in the literature, the Green Vehicle Routing Problem (GVRP), and competitive results have been obtained.     

Partial recharge strategies for the electric vehicle routing problem with time windows

The Electric Vehicle Routing Problem with Time Windows (EVRPTW) is an extension to the well-known Vehicle Routing Problem with Time Windows (VRPTW) where the fleet consists of electric vehicles (EVs). Since EVs have limited driving range due to their battery capacities they may need to visit recharging stations while servicing the customers along their route. The recharging may take place at any battery level and after the recharging the battery is assumed to be full. In this paper, we relax the full recharge restriction and allow partial recharging (EVRPTW-PR), which is more practical in the real world due to shorter recharging duration. We formulate this problem as a 0–1 mixed integer linear program and develop an Adaptive Large Neighborhood Search (ALNS) algorithm to solve it efficiently. We apply several removal and insertion mechanisms by selecting them dynamically and adaptively based on their past performances, including new mechanisms specifically designed for EVRPTW and EVRPTW-PR. These new mechanisms include the removal of the stations independently or along with the preceding or succeeding customers and the insertion of the stations with determining the charge amount based on the recharging decisions. We test the performance of ALNS by using benchmark instances from the recent literature. The computational results show that the proposed method is effective in finding high quality solutions and the partial recharging option may significantly improve the routing decisions.     

A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows

A heuristic algorithm is described for a time-constrained version of the advance-request, multi-vehicle, many-to-many Dial-A-Ride Problem (DARP). The time constraints consist of upper bounds on: (1) the amount of time by which the pick-up or delivery of a customer can deviate from the desired pick-up or delivery time; (2) the time that a customer can spend riding in a vehicle. The algorithm uses a sequential insertion procedure to assign customers to vehicles and to determine a time schedule of pick-ups and deliveries for each vehicle. A flexible objective function balances the cost of providing service with the customers' preferences for pick-up and delivery times close to those requested, and for short ride times. Computational experience with the algorithm is described, including a run with a real database of 2600 customers and some 20 simultaneously active vehicles. The scenario for the application of the algorithm is also discussed in detail.     

Solving the Fleet Size and Mix Vehicle Routing Problem with Time Windows via Adaptive Memory Programming

This paper presents a novel Adaptive Memory Programming (AMP) solution approach for the Fleet Size and Mix Vehicle Routing Problem with Time Windows (FSMVRPTW). The FSMVRPTW seeks to design a set of depot returning vehicle routes to service a set of customers with known demands, for a heterogeneous fleet of vehicles with different capacities and fixed costs. Each customer is serviced only once by exactly one vehicle, within fixed time intervals that represent the earliest and latest times during the day that service can take place. The objective is to minimize the total transportation costs, or similarly to determine the optimal fleet composition and dimension following least cost vehicle routes. The proposed method utilizes the basic concept of an AMP solution framework equipped with a probabilistic semi-parallel construction heuristic, a novel solution re-construction mechanism, an innovative Iterated Tabu Search algorithm tuned for intensification local search and frequency-based long term memory structures. Computational experiments on well-known benchmark data sets illustrate the efficiency and effectiveness of the proposed method. Compared to the current state-of-the-art, the proposed method improves the best reported cumulative and mean results over most problem instances with reasonable computational requirements.     

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.     

Design of multiple-vehicle delivery tours—I a ring-radial network

Certain aspects of what is commonly described as the “Vehicle Routing Problem” are discussed. We wish to deliver items to a large number of points randomly distributed over some region by means of vehicles, each of which can deliver to only C points. The key to any detailed routing to minimize the cost of delivery (by hand or computer) is first to partition the region into zones in which individual vehicles make deliveries. We assume here that there are many such zones, an average density of points δ, that the “unit of length” δ^-1/2 is large compared with the spacing between roads, and C ⪢ 1. To minimize the delivery cost, zones should be approximately rectangular in shape with a width comparable with δ^-1/2 and length comparable with Cδ^-1/2. In order to illustrate some numerical methods of approximation, we will first analyze, in considerable detail, the routing of vehicles on an idealized ring-radial network including how one would distort the shape of the zones near the origin and at boundaries. In Part II we will generalize this to other network geometries, and in Part III consider modifications in strategy if the items (people, for example) are valuable. In contrast with presently available computer programs for which the accuracy may decrease with increasing number of points in the region, the methods described here are essentially asymptotic approximations; the more points there are in the region, the more accurate are the results.     

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.     

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.     

Lifecycle modeling and assessment of unmanned aerial vehicles (Drones) CO2e emissions

There are no studies that model the potential effectiveness of Unmanned Aerial Vehicles (UAVs) or drones to reduce CO₂e lifecycle (including both utilization and vehicle phase) emissions when compared to conventional diesel vans, electric trucks, electric vans, and tricycles. This study presents a novel analysis of lifecycle UAV and ground commercial vehicles CO₂e emissions. Different route and customer configurations are modeled analytically. Utilizing real-word data, tradeoffs and comparative advantages of UAVs are discussed. Breakeven points for operational emissions are obtained and the results clearly indicate that UAVs are more CO₂e efficient, for small payloads, than conventional diesel vans in a per-distance basis. Drastically different results are obtained when customers can be grouped in a delivery route. UAV deliveries are not more CO₂e efficient than tricycle or electric van delivery services if a few customers can be grouped in a route. Vehicle phase CO₂e emissions for UAVs are significant and must be taken into account. Ground vehicles are more efficient when comparing vehicles production and disposal emissions per delivery.     

Greenhouse gas emission benefits of vehicle lightweighting: Monte Carlo probabalistic analysis of the multi material lightweight vehicle glider

Vehicle lightweighting reduces fuel cycle greenhouse gas (GHG) emissions but may increase vehicle cycle (production) GHG emissions because of the GHG intensity of lightweight material production. Life cycle GHG emissions are estimated and sensitivity and Monte Carlo analyses conducted to systematically examine the variables that affect the impact of lightweighting on life cycle GHG emissions. The study uses two real world gliders (vehicles without powertrain or battery) to provide a realistic basis for the analysis. The conventional and lightweight gliders are based on the Ford Fusion and Multi Material Lightweight Vehicle, respectively. These gliders were modelled with internal combustion engine vehicle (ICEV), hybrid electric vehicle (HEV), and battery electric vehicle (BEV) powertrains. The probability that using the lightweight glider in place of the conventional (steel-intensive) glider reduces life cycle GHG emissions are: ICEV, 100%; HEV, 100%, and BEV, 74%.The extent to which life cycle GHG emissions are reduced depends on the powertrain, which affects fuel cycle GHG emissions. Lightweighting an ICEV results in greater base case GHG emissions mitigation (10 t CO₂eq.) than lightweighting a more efficient HEV (6 t CO₂eq.). BEV lightweighting can result in higher or lower GHG mitigation than gasoline vehicles, depending largely on the source of electricity.     

Dynamic traffic routing in a network with adaptive signal control

In real traffic networks, travellers’ route choice is affected by traffic control strategies. In this research, we capture the interaction between travellers’ route choice and traffic signal control in a coherent framework. For travellers’ route choice, a VANET (Vehicular Ad hoc NETwork) is considered, where travellers have access to the real-time traffic information through V2V/V2I (Vehicle to Vehicle/Vehicle to Infrastructure) infrastructures and make route choice decisions at each intersection using hyper-path trees. We test our algorithm and control strategy by simulation in OmNet++ (A network communication simulator) and SUMO (Simulation of Urban MObility) under several scenarios. The simulation results show that with the proposed dynamic routing, the overall travel cost significantly decreases. It is also shown that the proposed adaptive signal control reduces the average delay effectively, as well as reduces the fluctuation of the average speed within the whole network.     

Sustainable urban transit network design

Sustainability is a requirement for modern public transportation networks, as these are expected to play a critical role in environment-friendly transportation systems. This paper focuses on developing an efficient model for solving a sustainable oriented variant of the Transit Route Network Design Problem. The model incorporates sustainable design objectives, considers emission-free (electric) vehicles and introduces a direct route design approach with route structure and directness control. An application in a real world case, highlights the performance and benefits of the proposed model.     

Service type assignment and container routing with transit time constraints and empty container repositioning for liner shipping service networks

A decision tool is developed for a liner shipping company to deploy its fleet considering vessel speeds and to find routes for cargos with repositioning of empty containers and transit time constraints. This problem is referred as the simultaneous Service type Assignment and container Routing Problem (SARP) in the sequel. A path-flow based mixed-integer linear programming formulation is suggested for the SARP. A Branch and Bound (BB) algorithm is used to solve the SARP exactly. A Column Generation (CG) procedure, embedded within the BB framework, is devised to solve the linear programming relaxation of the SARP. The CG subproblems arises as Shortest Path Problems (SPP). Yet incorporating transit time requirements yields constrained SPP which is NP-hard and solved by a label correcting algorithm. Computational experiments are performed on randomly generated test instances mimicking real life. The BB algorithm yields promising solutions for the SARP. The SARP with and without transit time constraints is compared with each other. Our results suggest a potential to increase profit margins of liner shipping companies by considering transit time requirements of cargos.     

Dynamic system-optimal traffic assignment using a state space model

We propose a new mathematical formulation for the problem of optimal traffic assignment in dynamic networks with multiple origins and destinations. This problem is motivated by route guidance issues that arise in an Intelligent Vehicle-Highway Systems (IVHS) environment. We assume that the network is subject to known time-varying demands for travel between its origins and destinations during a given time horizon. The objective is to assign the vehicles to links over time so as to minimize the total travel time experienced by all the vehicles using the network. We model the traffic network over the time horizon as a discrete-time dynamical system. The system state at each time instant is defined in a way that, without loss of optimality, avoids complete microscopic detail by grouping vehicles into platoons irrespective of origin node and time of entry to network. Moreover, the formulation contains no explicit path enumeration. The state transition function can model link travel times by either impedance functions, link outflow functions, or by a combination of both. Two versions (with different boundary conditions) of the problem of optimal traffic assignment are studied in the context of this model. These optimization problems are optimal control problems for nonlinear discrete-time dynamical systems, and thus they are amenable to algorithmic solutions based on dynamic programming. The computational challenges associated with the exact solution of these problems are discussed and some heuristics are proposed.     

A cooperative waiting strategy based on elliptical areas for the Dynamic Pickup and Delivery Problem with Time Windows

The purpose of this paper to present a cooperative scheduling algorithm for solving the Dynamic Pickup and Delivery Problem with Time Windows (DPDPTW). The idea behind cooperative waiting strategies is to calculate simultaneously the waiting times for all nodes in the solution. Classical non‐cooperative scheduling algorithms perform the scheduling for each route independently of the scheduling of the other routes. We present the Cooperative Scheduling Problem (CSP) based on the elliptical areas generated by vehicles waiting at their nodes. The CSP is solved by means of a genetic algorithm and is evaluated by using a set of benchmarks based on real‐life data found in the literature. Initially, two waiting strategies are presented: Wait‐Early‐Time scheduling and Balanced‐Departure scheduling. Extensive empirical simulations have been carried out by analyzing the degree of dynamism and the average waiting time, a new concept defined to take into account the gap between the time windows of pickup and delivery nodes. Copyright © 2016 John Wiley & Sons, Ltd.     

A rolling horizon algorithm for auto-carrier transportation

This paper introduces a rolling horizon algorithm to plan the delivery of vehicles to automotive dealers by a heterogeneous fleet of auto-carriers. The problem consists in scheduling the deliveries over a multiple-day planning horizon during which requests for transportation arrive dynamically. In addition, the routing of the auto-carriers must take into account constraints related to the loading of the vehicles on the carriers. The objective is to minimize the sum of traveled distances, fixed costs for auto-carrier operation, service costs, and penalties for late deliveries. The problem is solved by a heuristic that first selects the vehicles to be delivered in the next few days and then optimizes the deliveries by an iterated local search procedure. A branch-and-bound search is used to check the feasibility of the loading. To handle the dynamic nature of the problem, the complete algorithm is applied repeatedly in a rolling horizon framework. Computational results on data from a major European logistics service provider show that the heuristic is fast and yields significant improvements compared to the sequential solution of independent daily problems.     

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.     

Reducing CO2 emissions in temperature-controlled road transportation using the LDVRP model

Temperature-controlled transport is needed to maintain the quality of products such as fresh and frozen foods and pharmaceuticals. Road transportation is responsible for a considerable part of global emissions. Temperature-controlled transportation exhausts even more emissions than ambient temperature transport because of the extra fuel requirements for cooling and because of leakage of refrigerant. The transportation sector is under pressure to improve both its environmental and economic performance. To explore opportunities to reach this goal, the Load-Dependent Vehicle Routing Problem (LDVRP) model has been developed to optimize routing decisions taking into account fuel consumption and emissions related to the load of the vehicle. However, this model does not take refrigeration related emissions into account. We therefore propose an extension of the LDVRP model to optimize routing decisions and to account for refrigeration emissions in temperature-controlled transportation systems. This extended LDVRP model is applied in a case study in the Dutch frozen food industry. We show that taking the emissions caused by refrigeration in road transportation can result in different optimal routes and speeds compared with the LDVRP model and the standard Vehicle Routing Problem model. Moreover, taking the emissions caused by refrigeration into account improves the estimation of emissions related to temperature-controlled transportation. This model can help to reduce emissions of temperature-controlled road transportation.     

Ant Colony Routing algorithm for freeway networks

Dynamic traffic routing refers to the process of (re)directing vehicles at junctions in a traffic network according to the evolving traffic conditions. The traffic management center can determine desired routes for drivers in order to optimize the performance of the traffic network by dynamic traffic routing. However, a traffic network may have thousands of links and nodes, resulting in a large-scale and computationally complex non-linear, non-convex optimization problem. To solve this problem, Ant Colony Optimization (ACO) is chosen as the optimization method in this paper because of its powerful optimization heuristic for combinatorial optimization problems. ACO is implemented online to determine the control signal – i.e., the splitting rates at each node. However, using standard ACO for traffic routing is characterized by four main disadvantages: 1. traffic flows for different origins and destinations cannot be distinguished; 2. all ants may converge to one route, causing congestion; 3. constraints cannot be taken into account; and 4. neither can dynamic link costs. These problems are addressed by adopting a novel ACO algorithm with stench pheromone and with colored ants, called Ant Colony Routing (ACR). Using the stench pheromone, the ACR algorithm can distribute the vehicles over the traffic network with less or no traffic congestion, as well as reduce the number of vehicles near some sensitive zones, such as hospitals and schools. With colored ants, the traffic flows for multiple origins and destinations can be represented. The proposed approach is also implemented in a simulation-based case study in the Walcheren area, the Netherlands, illustrating the effectiveness of the approach.     

Vehicle routing with roaming delivery locations

We propose the vehicle routing problem with roaming delivery locations (VRPRDL) to model an innovation in last-mile delivery where a customer’s order is delivered to the trunk of his car. We develop construction and improvement heuristics for the VRPRDL based on two problem-specific techniques: (1) efficiently optimizing the delivery locations for a fixed customer delivery sequence and (2) efficiently switching a predecessor’s or successor’s delivery location during the insertion or deletion of a customer in a route. Furthermore, we conduct an extensive computation study to assess and quantify the benefits of trunk delivery in a variety of settings. The study reveals that a significant reduction in total distance travelled can be achieved, especially when trunk delivery is combined with traditional home delivery, which has both economic and environmental benefits.