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.     

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.     

Design and development of a hybrid artificial bee colony algorithm for the environmental vehicle routing problem

The vehicle routing problem (VRP) is a critical and vital problem in logistics for the design of an effective and efficient transportation network, within which the capacitated vehicle routing problem (CVRP) has been widely studied for several decades due to the practical relevance of logistics operation. However, CVRP with the objectives of minimizing the overall traveling distance or the traveling time cannot meet the latest requirements of green logistics, which concern more about the influence on the environment. This paper studies CVRP from an environmental perspective and introduces a new model called environmental vehicle routing problem (EVRP) with the aim of reducing the adverse effect on the environment caused by the routing of vehicles. In this research, the environmental influence is measured through the amount of the emission carbon dioxide, which is a widely acknowledged criteria and accounts for the major influence on environment. A hybrid artificial bee colony algorithm (ABC) is designed to solve the EVRP model, and the performance of the hybrid algorithm is evaluated through comparing with well-known CVRP instances. The computational results from numerical experiments suggest that the hybrid ABC algorithm outperforms the original ABC algorithm by 5% on average. The transformation from CVRP to EVRP can be recognized through the differentiation of their corresponding optimal solutions, which provides practical insights for operation management in green logistics.     

Customized bus service design for jointly optimizing passenger-to-vehicle assignment and vehicle routing

Emerging transportation network services, such as customized buses, hold the promise of expanding overall traveler accessibility in congested metropolitan areas. A number of internet-based customized bus services have been planned and deployed for major origin-destination (OD) pairs to/from inner cities with limited physical road infrastructure. In this research, we aim to develop a joint optimization model for addressing a number of practical challenges for providing flexible public transportation services. First, how to maintain minimum loading rate requirements and increase the number of customers per bus for the bus operators to reach long-term profitability. Second, how to optimize detailed bus routing and timetabling plans to satisfy a wide range of specific user constraints, such as passengers’ pickup and delivery locations with preferred time windows, through flexible decision for matching passengers to bus routes. From a space-time network modeling perspective, this paper develops a multi-commodity network flow-based optimization model to formulate a customized bus service network design problem so as to optimize the utilization of the vehicle capacity while satisfying individual demand requests defined through space-time windows. We further develop a solution algorithm based on the Lagrangian decomposition for the primal problem and a space-time prism based method to reduce the solution search space. Case studies using both the illustrative and real-world large-scale transportation networks are conducted to demonstrate the effectiveness of the proposed algorithm and its sensitivity under different practical operating conditions.     

Optimal solution to the vehicle routing problem by adopting a meta-heuristic algorithm

The delivery service provided by large-scale retailers continues to grow as online sales occupy an increasingly large share of the market. This study aims to tease out efficient vehicle scheduling times as well as optimal delivery routes by applying meta-heuristic algorithms. Monthly data on existing routes were obtained from a branch of Korea’s leading large-scale online retailer. The first task was to examine the status of existing routes by comparing delivery routes created using Dijkstra’s algorithm with existing delivery routes and their vehicle scheduling. The second task was to identify optimal delivery routes through a comparative analysis of the genetic algorithm and Tabu search algorithm, known for its superior applicability amongst other meta-heuristic algorithms. These findings demonstrate that the optimal vehicle routing problem not only has the potential to reduce distribution costs for operators and expedite delivery for consumers, but also the added social benefit of reduced carbon emissions.     

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.     

Order-first split-second methods for vehicle routing problems: A review

Cluster-first route-second methods like the sweep heuristic (Gillett and Miller, 1974) are well known in vehicle routing. They determine clusters of customers compatible with vehicle capacity and solve a traveling salesman problem for each cluster. The opposite approach, called route-first cluster-second, builds a giant tour covering all customers and splits it into feasible trips. Cited as a curiosity for a long time but lacking numerical evaluation, this technique has nevertheless led to successful metaheuristics for various vehicle routing problems in the last decade. As many implementations consider an ordering of customers instead of building a giant tour, we propose in this paper the more general name of ordering-first split-second methods. This article shows how this approach can be declined for different vehicle routing problems and reviews the associated literature, with more than 70 references.     

Integrated scheduling of m-truck,m-drone,and m-depot constrained by time-window,drop-pickup,and m-visit using constraint programming

The idea of deploying unmanned aerial vehicles, also known as drones, for final-mile delivery in logistics operations has vitalized this new research stream. One conceivable scenario of using a drone in conjunction with a traditional delivery truck to distribute parcels is discussed in earlier literature and termed the parallel drone scheduling traveling salesman problem (PDSTSP). This study extends the problem by considering two different types of drone tasks: drop and pickup. After a drone completes a drop, the drone can either fly back to depot to deliver the next parcels or fly directly to another customer for pickup. Integrated scheduling of multiple depots hosting a fleet of trucks and a fleet of drones is further studied to achieve an operational excellence. A vehicle that travels near the boundary of the coverage area might be more effective to serve customers that belong to the neighboring depot. This problem is uniquely modeled as an unrelated parallel machine scheduling with sequence dependent setup, precedence-relationship, and reentrant, which gives us a framework to effectively consider those operational challenges. A constraint programming approach is proposed and tested with problem instances of m-truck, m-drone, m-depot, and hundred-customer distributed across an 8-mile square region.     

The performance of route modification and demand stabilization strategies in stochastic vehicle routing

A key concern in managing vehicle routing operations under stochastic demands is whether, on the basis of travel distance, route modification yields materially greater logistical efficiency than fixed routes. This research uses statistical calibration as the primary technique to develop a robust and tractable model for estimating this difference in logistical efficiency. Based on features such as the models predictive accuracy and generalizability, it constitutes a substantive improvement over existing models. The present study also expands the range of predictive models relevant to vehicle routing under stochastic demands with models to estimate the transportation and inventory effects of persuading customers to stabilize their ordering patterns.     

The vehicle platooning problem: Computational complexity and heuristics

We create a mathematical framework for modeling trucks traveling in road networks, and we define a routing problem called the platooning problem. We prove that this problem is NP-hard, even when the graph used to represent the road network is planar. We present integer linear programming formulations for instances of the platooning problem where deadlines are discarded, which we call the unlimited platooning problem. These allow us to calculate fuel-optimal solutions to the platooning problem for large-scale, real-world examples. The problems solved are orders of magnitude larger than problems previously solved exactly in the literature. We present several heuristics and compare their performance with the optimal solutions on the German Autobahn road network. The proposed heuristics find optimal or near-optimal solutions in most of the problem instances considered, especially when a final local search is applied. Assuming a fuel reduction factor of 10% from platooning, we find fuel savings from platooning of 1–2% for as few as 10 trucks in the road network; the percentage of savings increases with the number of trucks. If all trucks start at the same point, savings of up to 9% are obtained for only 200 trucks.     

The time-dependent vehicle routing problem with soft time windows and stochastic travel times

This paper studies a vehicle routing problem with time-dependent and stochastic travel times. In our problem setting, customers have soft time windows. A mathematical model is used in which both efficiency for service as well as reliability for customers are taken into account. Depending on whether service times are included or not, we consider two versions of this problem. Two metaheuristics are built: a Tabu Search and an Adaptive Large Neighborhood Search. We carry out our experiments for well-known problem instances and perform comprehensive analyses on the numerical results in terms of the computational time and the solution quality. Experiments confirm that the proposed procedure is effective to obtain very good solutions to be performed in real-life environment.     

A differential evolution approach for the vehicle routing problem with backhauls and time windows

This paper presents a differential evolution algorithm (DEA) to solve a vehicle routing problem with backhauls and time windows (VRPBTW) and applied for a catering firm. VRPBTW is an extension of the vehicle routing problem, which includes capacity and time window constraints. In this problem, customers are divided into two subsets: linehaul and backhaul. Each vehicle starts from a depot and goods are delivered from the depot to the linehaul customers. Goods are subsequently brought back to the depot from the backhaul customers. The objective is to minimize the total distance that satisfies all of the constraints. The problem is formulated using mixed integer programming and solved using DEA. Proposed algorithm is tested with several benchmark problems to demonstrate effectiveness and efficiency of the algorithm and results show that our proposed algorithm can find superior solutions for most of the problems in comparison with the best known solutions. Hence, DEA was carried out for catering firm to minimize total transportation costs. Copyright © 2013 John Wiley & Sons, Ltd.     

Design and development of a hybrid ant colony-variable neighbourhood search algorithm for a multi-depot green vehicle routing problem

The traditional distribution planning problem in a supply chain has often been studied mainly with a focus on economic benefits. The growing concern about the effects of anthropogenic pollutions has forced researchers and supply chain practitioners to address the socio-environmental concerns. This research study focuses on incorporating the environmental impact on route design problem. In this work, the aim is to integrate both the objectives, namely economic cost and emission cost reduction for a capacitated multi-depot green vehicle routing problem. The proposed models are a significant contribution to the field of research in green vehicle routing problem at the operational level. The formulated integer linear programming model is solved for a set of small scale instances using LINGO solver. A computationally efficient Ant Colony Optimization (ACO) based meta-heuristic is developed for solving both small scale and large scale problem instances in reasonable amount of time. For solving large scale instances, the performance of the proposed ACO based meta-heuristic is improved by integrating it with a variable neighbourhood search.     

Vehicle routing problem and driver behaviour: a review and framework for analysis

Vehicle routing problems (VRPs) whose typical objective is to minimise total travel costs over a tour have evolved over the years with objectives ranging from minimising travel times and distances to minimising pollution and fuel consumption. However, driver behaviour continues to be neglected while planning for vehicle routes. Factors such as traffic congestion levels, monotonous drives and fatigue have an impact on the behaviour of drivers, which in turn might affect their speed-choice and route-choice behaviours. The behaviour of drivers and their subsequent decision-making owing to these factors impact the revenue of transport companies and could lead to huge losses in extreme cases. There have been studies on the behaviour of drivers in isolation, without inclusion of the objectives and constraints of the traditional routing problem. This paper presents a review of existing models of VRP, planner behaviour models in the VRP context and driver behaviour models and provides a motivation to integrate these models in a stochastic traffic environment to produce practical, economic and driver-friendly logistics solutions. The paper provides valuable insights on the relevance of behavioural issues in logistics and highlights the modelling implications of incorporating planner and driver behaviour in the framework of routing problems.     

An integrated modelling approach for the bicriterion vehicle routing and scheduling problem with environmental considerations

The consideration of pollution in routing decisions gives rise to a new routing framework where measures of the environmental implications are traded off with business performance measures. To address this type of routing decisions, we formulate and solve a bi-objective time, load and path-dependent vehicle routing problem with time windows (BTL-VRPTW). The proposed formulation incorporates a travel time model representing realistically time varying traffic conditions. A key feature of the problem under consideration is the need to address simultaneously routing and path finding decisions. To cope with the computational burden arising from this property of the problem we propose a network reduction approach. Computational tests on the effect of the network reduction approach on determining non-dominated solutions are reported. A generic solution framework is proposed to address the BTL-VRPTW. The proposed framework combines any technique that creates capacity-feasible routes with a routing and scheduling method that aims to convert the identified routes to problem solutions. We show that transforming a set of routes to BTL-VRPTW solutions is equivalent to solving a bi-objective time dependent shortest path problem on a specially structured graph. We propose a backward label setting technique to solve the emerging problem that takes advantage of the special structure of the graph. The proposed generic solution framework is implemented by integrating the routing and scheduling method into an Ant Colony System algorithm. The accuracy of the proposed algorithm was assessed on the basis of its capability to determine minimum travel time and fuel consumption solutions. Although the computational results are encouraging, there is ample room for future research in algorithmic advances on addressing the proposed problem.     

The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery

Once limited to the military domain, unmanned aerial vehicles are now poised to gain widespread adoption in the commercial sector. One such application is to deploy these aircraft, also known as drones, for last-mile delivery in logistics operations. While significant research efforts are underway to improve the technology required to enable delivery by drone, less attention has been focused on the operational challenges associated with leveraging this technology. This paper provides two mathematical programming models aimed at optimal routing and scheduling of unmanned aircraft, and delivery trucks, in this new paradigm of parcel delivery. In particular, a unique variant of the classical vehicle routing problem is introduced, motivated by a scenario in which an unmanned aerial vehicle works in collaboration with a traditional delivery truck to distribute parcels. We present mixed integer linear programming formulations for two delivery-by-drone problems, along with two simple, yet effective, heuristic solution approaches to solve problems of practical size. Solutions to these problems will facilitate the adoption of unmanned aircraft for last-mile delivery. Such a delivery system is expected to provide faster receipt of customer orders at less cost to the distributor and with reduced environmental impacts. A numerical analysis demonstrates the effectiveness of the heuristics and investigates the tradeoffs between using drones with faster flight speeds versus longer endurance.     

An analysis of the effects of French vehicle inspection program and grant for scrappage on household vehicle transaction

The French government has implemented a periodical vehicle inspection program, which aims at maintaining proper functioning of the vehicle and ensuring the emissions control systems installed on the vehicle work properly. Also, an incentive program for scrapping old vehicles was introduced in 1994 through 1996 to promote the replacement of those vehicles with higher emissions by newer vehicles with lower emissions. A hazard-based duration model of household vehicle transaction behavior has been developed in this study to examine the effects of the inspection program and the grant for scrappage on vehicle transaction timing. The model is developed as a competing risks model assuming the following three types of competing risks: replacing one of the vehicles in the household fleet, disposing of one vehicle in the fleet, and acquiring one vehicle to add to the fleet. The empirical analysis is carried out using the panel data of French households' vehicle ownership from 1984 to 1998, obtained by the panel survey called Parc-Auto, which has been conducted by a French marketing firm, SOFRES, since 1976. The long panel observation period facilitates the introduction of macro-economic indicators into the model, enabling the analysis to distinguish the effects of policy measures from macro-economic factors. The empirical results indicate that the expected vehicle holding duration becomes 1.3 years longer under the inspection program than before the program commenced, given that the vehicle is replaced by another vehicle at the end of the holding duration; and that the conditional probability of replacing a vehicle aged 10 years and over becomes 1.2 times higher, and the average holding duration becomes shorter by 3.3 years, when the grant for scrappage is available.     

Dynamic autonomous vehicle fleet operations: Optimization-based strategies to assign AVs to immediate traveler demand requests

Motivated by the growth of ridesourcing services and the expected advent of fully-autonomous vehicles (AVs), this paper defines, models, and compares assignment strategies for a shared-use AV mobility service (SAMS). Specifically, the paper presents the on-demand SAMS with no shared rides, defined as a fleet of AVs, controlled by a central operator, that provides direct origin-to-destination service to travelers who request rides via a mobile application and expect to be picked up within a few minutes. The underlying operational problem associated with the on-demand SAMS with no shared rides is a sequential (i.e. dynamic or time-dependent) stochastic control problem. The AV fleet operator must assign AVs to open traveler requests in real-time as traveler requests enter the system dynamically and stochastically. As there is likely no optimal policy for this sequential stochastic control problem, this paper presents and compares six AV-traveler assignment strategies (i.e. control policies). An agent-based simulation tool is employed to model the dynamic system of AVs, travelers, and the intelligent SAMS fleet operator, as well as, to compare assignment strategies across various scenarios. The results show that optimization-based AV-traveler assignment strategies, strategies that allow en-route pickup AVs to be diverted to new traveler requests, and strategies that incorporate en-route drop-off AVs in the assignment problem, reduce fleet miles and decrease traveler wait times. The more-sophisticated AV-traveler assignment strategies significantly improve operational efficiency when fleet utilization is high (e.g. during the morning or evening peak); conversely, when fleet utilization is low, simply assigning traveler requests sequentially to the nearest idle AV is comparable to more-advanced strategies. Simulation results also indicate that the spatial distribution of traveler requests significantly impacts the empty fleet miles generated by the on-demand SAMS.     

Robust weekly aircraft maintenance routing problem and the extension to the tail assignment problem

In this paper, we study two closely related airline planning problems: the robust weekly aircraft maintenance routing problem (RWAMRP) and the tail assignment problem (TAP). In real life operations, the RWAMRP solution is used in tactical planning whereas the TAP solution is implemented in operational planning. The main objective of these two problems is to minimize the total expected propagated delay (EPD) of the aircraft routes. To formulate the RWAMRP, we propose a novel weekly line-of-flights (LOF) network model that can handle complex and nonlinear cost functions of EPD. Because the number of LOFs grows exponentially with the number of flights to be scheduled, we propose a two-stage column generation approach to efficiently solve large-scale real-life RWAMRPs. Because the EPD of an LOF is highly nonlinear and can be very time-consuming to accurately compute, we propose three lower bounds on the EPD to solve the pricing subproblem of the column generation. Our approach is tested on eight real-life test instances. The computational results show that the proposed approach provides very tight LP relaxation (within 0.6% of optimal solutions) and solves the test case with more than 6000 flights per week in less than three hours. We also investigate the solutions obtained by our approach over 500 simulated realizations. The simulation results demonstrate that, in all eight test instances, our solutions result in less EPDs than those obtained from traditional methods. We then extend our model and solution approach to solve realistically simulated TAP instances.     

The Vehicle Routing Problem: The Case of the Hong Kong Postal Service

Abstract

With the growth in population and development of business activities in Hong Kong, the range and level of services provided by Hongkong Post have multiplied. However, the schedule of its postal vehicles, including mail collection and delivery, is still constructed manually on a daily basis, based on the experience of staff and transportation reviews. In this paper, the problem of scheduling a set of n collection points (District Post Offices) from a depot (General Post Office) in Hong Kong Island is addressed. The objectives pursued are the maximization of resource utilization and minimization of operation costs. In other words, the variable cost is expected to be reduced. To achieve these goals, an integer linear programming (IP) model of the vehicle routing problem (VRP) is developed in an effort to obtain optimal solutions. As the model involves computational complexity, a commercial software package CPLEX is used to solve the problems efficiently. The results show that the proposed model can produce optimal vehicle routes and schedules.