The two-echelon time-constrained vehicle routing problem in linehaul-delivery systems considering carbon dioxide emissions

Multi-echelon distribution strategy is primarily to alleviate the environmental (e.g., energy consumption and emissions) consequence of logistics operations. Differing from the long-term strategic problems (e.g., the two-echelon vehicle routing problem (2E-VRP), the two-echelon location routing problem (2E-LRP) and the truck and trailer routing problem (TTRP)) that make location decisions in depots or satellites, the paper introduces a short-term tactical problem named the two-echelon time-constrained vehicle routing problem in linehaul-delivery systems (2E-TVRP) considering carbon dioxide (CO₂) emissions. The linehaul level and the delivery level are linked through city distribution centers (CDCs). The 2E-TVRP, which takes CO₂ emissions per ton-kilometer as the objective, has inter-CDC linehaul on the 1st level and delivery from CDCs to satellites on the 2nd level. The Clarke and Wright savings heuristic algorithm (CW) improved by a local search phase is put forward. The case study shows the applicability of the model to real-life problems. The results suggest that the vehicle scheduling provided by the 2E-TVRP is promising to reduce the CO₂ emissions per ton-kilometer of the linehaul-delivery system. Adjusting the central depot location or developing the loaded-semitrailer demand among O-D pairs to eliminate empty-running of tractors will contribute to reduce the CO₂ emission factor.     

The two-echelon time-constrained vehicle routing problem in linehaul-delivery systems

Most of the studies address issues relating to the delivery from satellites to customers, which is throughout the end part of the linehaul-delivery system. Differing from the long-term strategic problems including the two-echelon vehicle routing problem (2E-VRP), the two-echelon location routing problem (2E-LRP) and the truck and trailer routing problem (TTRP) which make location decisions in depots or satellites, the paper introduces a short-term tactical problem named the two-echelon time-constrained vehicle routing problem in linehaul-delivery systems (2E-TVRP) that does not involve location decisions. The linehaul level and the delivery level are linked through city distribution centers (CDCs) located on the outskirts of cities. The 2E-TVRP has inter-CDC linehaul on the first level and urban delivery from CDCs to satellites on the second level. Vehicle routes on different levels are interacted by time constraints. A mixed integer nonlinear programming model for the 2E-TVRP is put forward, and a mixed integer linear programming model is used as the benchmark model. The Clarke and Wright savings heuristic algorithm (CW) improved by a local search phase is adopted. The 2E-TVRP formulations and the heuristic algorithm are tested by using 140 randomly-generated instances with up to 10 CDCs and 500 satellites. The computational results indicate that the heuristic can effectively solve various instances of the 2E-TVRP.     

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.     

Analysis of an O(N2) heuristic for the single vehicle many-to-many Euclidean dial-a-ride problem

We develop an O(N²) heuristic to solve the single vehicle many-to-many Euclidean Dial-A-Ride problem. The heuristic is based on the Minimum Spanning Tree of the modes of the problem. The algorithm's worst case performance is four times the length of the optimal Dial-A-Ride tour. An analysis of the algorithm's average performance reveals that in terms of sizes of single-vehicle problems that are likely to be encountered in the real world (up to 100 nodes) and in terms of computational complexity, the O(N²) heuristic performs equally well, or, in many cases, better than heuristics described earlier by Stein for the same problem. The performance of the heuristic exhibits statistical stability over a broad range of problem sizes.     

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.     

Route design for last-in,first-out deliveries with backhauling

The retail route design problem extends the capacitated vehicle routing problem with time windows by introducing several operational constraints, including order loading and delivery restrictions (last-in, first-out), order-dependent vehicle capacity, material handling limits at the warehouse, backhauling, and driving time bounds. In this paper, the problem is modeled on a directed network for an application associated with a major grocery chain. Because the corresponding mixed-integer program proved too difficult to solve with commercial software for real instances, we developed a greedy randomized adaptive search procedure (GRASP) augmented with tabu search to provide solutions. Testing was done using data sets provided Kroger, the largest grocery chain in the US, and benchmarked against a previously developed column generation algorithm. The results showed that cost reductions of $4887 per day or 5.58% per day on average, compared to Kroger’s corresponding solutions.     

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.     

Stochastic optimal path problem with relays

This paper studies the optimal path problem for travelers driving with vehicles of a limited range, such as most battery electric vehicles currently available in the market. The optimal path in this problem often consists of several relay points, where the vehicles can be refueled to extend its range. We propose a stochastic optimal path problem with relays (SOPPR), which aims at minimizing a general expected cost while maintaining a reasonable arrival probability. To account for uncertainty in the road network, the travel speed on a road segment is treated as a discrete random variable, which determines the total energy required to traverse the segment. SOPPR is formulated in two stages in this paper. In the first stage, an optimal routing problem is solved repeatedly to obtain the expected costs and arrival probabilities from any node to all refueling nodes and the destination. With this information, the second stage constructs an auxiliary network, on which the sequence of refueling decisions can be obtained by solving another optimal path problem. Label-correcting algorithms are developed to solve the routing problems in both stages. Numerical experiments are conducted to compare the stochastic and deterministic models, to examine the impact of different parameters on the routing results, and to evaluate the computational performance of the proposed algorithms.     

Solving the bicriterion routing and scheduling problem for hazardous materials distribution

Hazardous materials routing and scheduling decisions involve the determination of the minimum cost and/or risk routes for servicing the demand of a given set of customers. This paper addresses the bicriterion routing and scheduling problem arising in hazardous materials distribution planning. Under the assumption that the cost and risk attributes of each arc of the underlying transportation network are time-dependent, the proposed routing and scheduling problem pertains to the determination of the non-dominated time-dependent paths for servicing a given and fixed sequence of customers (intermediate stops) within specified time windows. Due to the heavy computational burden for solving this bicriterion problem, an alternative algorithm is proposed that determines the k-shortest time-dependent paths. Moreover an algorithm is provided for solving the bicriterion problem. The proximity of the solutions of the k-shortest time-dependent path problem with the non-dominated solutions is assessed on a set of problems developed by the authors.     

Integrated smart feeder/shuttle transit service: simulation of new routing strategies

The idea of designing an integrated smart feeder/shuttle service stemmed from the need to overcome the problem of using an excessive number of cars arriving and parking at a train station within the same time span. This problem results in high parking demand around the train station. Moreover, some potential train riders will, instead, use their cars and hence become a party to increasing the traffic congestion. This work develops a new idea of an integrated and innovative feeder/shuttle system with new operating and routing concepts. The fulfilled objectives are as follows: (i) to construct and examine different operating strategies from both the user and operator perspectives; (ii) to examine different routing models and scenarios; and (iii) to construct a simulation tool for (i) and (ii). Ten different routing strategies are examined, with all the combinations of fixed/flexible routes, fixed/flexible schedules, a unidirectional or bidirectional concept, and shortcut (shortest path) and/or short‐turn (turnaround) concepts. These strategies are investigated by employing a simulation model specifically developed and constructed for this purpose. This simulation model is used in a case study of Castro Valley in California in which the feeder/shuttle service is coordinated with the Bay Area Rapid Transit service, and the 10 routing strategies are compared in regard to four fleet‐size scenarios. One of the interesting results found is that the fixed‐route and flexible‐route concepts are comparable in performance measures when applying a combination of operating strategies. Copyright © 2011 John Wiley & Sons, Ltd.     

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.     

Passenger-demands-oriented train scheduling for an urban rail transit network

This paper considers the train scheduling problem for an urban rail transit network. We propose an event-driven model that involves three types of events, i.e., departure events, arrival events, and passenger arrival rates change events. The routing of the arriving passengers at transfer stations is also included in the train scheduling model. Moreover, the passenger transfer behavior (i.e., walking times and transfer times of passengers) is also taken into account in the model formulation. The resulting optimization problem is a real-valued nonlinear nonconvex problem. Nonlinear programming approaches (e.g., sequential quadratic programming) and evolutionary algorithms (e.g., genetic algorithms) can be used to solve this train scheduling problem. The effectiveness of the event-driven model is evaluated through a case study.     

Multi-objective optimization of train routing problem combined with train scheduling on a high-speed railway network

Based on train scheduling, this paper puts forward a multi-objective optimization model for train routing on high-speed railway network, which can offer an important reference for train plan to provide a better service. The model does not only consider the average travel time of trains, but also take the energy consumption and the user satisfaction into account. Based on this model, an improved GA is designed to solve the train routing problem. The simulation results demonstrate that the accurate algorithm is suitable for a small-scale network, while the improved genetic algorithm based on train control (GATC) applies to a large-scale network. Finally, a sensitivity analysis of the parameters is performed to obtain the ideal parameters; a perturbation analysis shows that the proposed method can quickly handle the train disturbance.     

An iterative route construction and improvement algorithm for the vehicle routing problem with soft time windows

The solution of routing problems with soft time windows has valuable practical applications. Soft time window solutions are needed when: (a) the number of routes needed for hard time windows exceeds the number of available vehicles, (b) a study of cost-service tradeoffs is required, or (c) the dispatcher has qualitative information regarding the relative importance of hard time-window constraints across customers. This paper proposes a new iterative route construction and improvement algorithm to solve vehicle routing problems with soft time windows. Due to its modular and hierarchical design, the solution algorithm is intuitive and able to accommodate general cost and penalty functions. Experimental results indicate that the average run time performance is of order O(n²). The solution quality and computational time of the new algorithm has been compared against existing results on benchmark problems. The presented algorithm has improved thirty benchmark problem solutions for the vehicle routing problems with soft time windows.     

A reinforcement learning framework for the adaptive routing problem in stochastic time-dependent network

Most previous work in addressing the adaptive routing problem in stochastic and time-dependent (STD) network has been focusing on developing parametric models to reflect the network dynamics and designing efficient algorithms to solve these models. However, strong assumptions need to be made in the models and some algorithms also suffer from the curse of dimensionality. In this paper, we examine the application of Reinforcement Learning as a non-parametric model-free method to solve the problem. Both the online Q learning method for discrete state space and the offline fitted Q iteration algorithm for continuous state space are discussed. With a small case study on a mid-sized network, we demonstrate the significant advantages of using Reinforcement Learning to solve for the optimal routing policy over traditional stochastic dynamic programming method. And the fitted Q iteration algorithm combined with tree-based function approximation is shown to outperform other methods especially during peak demand periods.     

Just-in-time delivery for green fleets: A feedback control approach

With increasing attention being paid to greenhouse gas (GHG) emissions, the transportation industry has become an important focus of approaches to reduce GHG emissions, especially carbon dioxide equivalent (CO₂e) emissions. In this competitive industry, of course, any new emissions reduction technique must be economically attractive and contribute to good operational performance. In this paper, a continuous-variable feedback control algorithm called GEET (Greening via Energy and Emissions in Transportation) is developed; customer deliveries are assigned to a fleet of vehicles with the objective function of Just-in-Time (JIT) delivery and fuel performance metrics akin to the vehicle routing problem with soft time windows (VRPSTW). GEET simultaneously determines vehicle routing and sets cruising speeds that can be either fixed for the entire trip or varied dynamically based on anticipated performance. Dynamic models for controlling vehicle cruising speed and departure times are proposed, and the impact of cruising speed on JIT performance and fuel performance are evaluated. Allowing GEET to vary cruising speed is found to produce an average of 12.0–16.0% better performance in fuel cost, and −36.0% to +16.0% discrepancy in the overall transportation cost as compared to the Adaptive Large Neighborhood Search (ALNS) heuristic for a set of benchmark problems. GEET offers the advantage of extremely fast computational times, which is a substantial strength, especially in a dynamic transportation environment.     

A decision support system for integrated hazardous materials routing and emergency response decisions

Hazardous materials routing constitutes a critical decision in mitigating the associated transportation risk. This paper presents a decision support system for assessing alternative distribution routes in terms of travel time, risk and evacuation implications while coordinating the emergency response deployment decisions with the hazardous materials routes. The proposed system provides the following functionalities: (i) determination of alternative non-dominated hazardous materials distribution routes in terms of cost and risk minimization, (ii) specification of the hazardous materials first-response emergency service units locations in order to achieve timely response to an accident, and (iii) determination of evacuation paths from the impacted area to designated shelters and estimation of the associated evacuation time. The proposed system has been implemented, used and evaluated for assessing alternative hazardous materials routing decisions within the heavily industrialized area of Thriasion Pedion of Attica, Greece. The implementation of the aforementioned functionalities is based on two new integer programming models for the hazardous materials routing and the emergency response units location problems, respectively. A simplified version of the routing model is solved by an existing heuristic algorithm developed by the authors. A new Lagrangean relaxation heuristic algorithm has been developed for solving the emergency response units location problem. The focus of this paper is on the exposition of the proposed decision support system components and functionalities. Special emphasis is placed on the presentation of the two new mathematical models and the new solution method for the location model.     

The impact of depot location,fleet composition and routing on emissions in city logistics

This paper investigates the combined impact of depot location, fleet composition and routing decisions on vehicle emissions in city logistics. We consider a city in which goods need to be delivered from a depot to customers located in nested zones characterized by different speed limits. The objective is to minimize the total depot, vehicle and routing cost, where the latter can be defined with respect to the cost of fuel consumption and CO₂ emissions. A new powerful adaptive large neighborhood search metaheuristic is developed and successfully applied to a large pool of new benchmark instances. Extensive analyses are performed to empirically assess the effect of various problem parameters, such as depot cost and location, customer distribution and heterogeneous vehicles on key performance indicators, including fuel consumption, emissions and operational costs. Several managerial insights are presented.     

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 tailored branch-and-price approach for a joint tramp ship routing and bunkering problem

This paper deals with a practical tramp ship routing problem while taking into account different bunker prices at different ports, which is called the joint tramp ship routing and bunkering (JSRB) problem. Given a set of cargoes to be transported and a set of ports with different bunker prices, the proposed problem determines how to route ships to carry the cargoes and the amount of bunker to purchase at each port, in order to maximize the total profit. After building an integer linear programming model for the JSRB problem, we propose a tailored branch-and-price (B&P) solution approach. The B&P approach incorporates an efficient method for obtaining the optimal bunkering policy and a novel dominance rule for detecting inefficient routing options. The B&P approach is tested with randomly generated large-scale instances derived from real-world planning problems. All of the instances can be solved efficiently. Moreover, the proposed approach for the JSRB problem outperforms the conventional sequential planning approach and can incorporate the prediction of future cargo demand to avoid making myopic decisions.