Adaptive memory programming for the vehicle routing problem with multiple trips

doi:10.1016/j.cor.2005.02.044

Computers & Operations Research

Volume 34, Issue 1, January 2007, Pages 28-47

https://doi.org/10.1016/j.cor.2005.02.044 Get rights and content

Abstract

The Vehicle Routing Problem with Multiple Trips is an extension of the classical Vehicle Routing Problem in which each vehicle may perform several routes in the same planning period. In this paper, an adaptive memory algorithm to solve this problem is proposed. Computational experience is reported over a set of benchmark problem instances.

Introduction

The problem of distributing goods from depots to final consumers plays an important role in the management of many distribution systems, and its adequate programming may produce significant savings. The Vehicle Routing Problem (VRP) and its many variations have been subject of research during the last four decades. Some well studied characteristics include the existence of demands, time windows and heterogeneous vehicles [1].

However, some aspects that arise in real applications have not received much attention in the Operations Research literature. For instance, it usually assumed that each vehicle may perform at most one route in the same planning period, and in many cases the number of available vehicles is supposed to be unlimited. In many practical applications, this assumptions are unrealistic. When the vehicle capacity is small or when the planning period is large, performing more than one route per vehicle may be the only practical solution. In urban areas, where travel times are rather small, it is often the case that after performing short tours vehicles are reloaded and used again.

The Vehicle Routing Problem with Multiple Trips (VRPMT) overcomes the mentioned limitations, besides considering the classic VRP constraints. Solving the VRPMT not only implies the design of a set of routes, but the assignment of those routes to the available vehicles. This makes the VRPMT a very practical problem, specially at an operational level, in which daily driver schedules must be designed for a fixed vehicle fleet.

In this paper we describe a heuristic to solve the VRPMT, which is based on the Adaptive Memory Procedure (AMP) proposed by Rochat and Taillard [2]. A definition of the VRPMT is given in Section 2, as well as a literature review. The proposed algorithm is described in Section 3. Computational behavior of the algorithm is reported and analyzed in Section 4, while conclusions and future work are considered in Section 5.

Section snippets

The VRP with multiple trips

Let $G = (V, E)$ be a graph where $V = {0, 1, \dots, n}$ is the set of nodes and $E \subseteq V \times V$ is the set of arcs. If $(i, j) \in E$ , then it is possible to travel from i to j, incurring in a cost $c_{ij}$ and a travel time $t_{ij}$ . Node 0 represents a depot where a fleet $K = {1, \dots, m}$ of identical vehicles is based. Each vehicle has a limited capacity Q. The nodes in $V ⧹ {0}$ represent customers, each one having a demand $q_{i}$ . Finally, there exists a time horizon, denoted by T, which establishes the duration of a working day. It is assumed

Adaptive memory algorithm

The AMP was first proposed by Rochat and Taillard [2] as an enhancement of Tabu Search (TS) to solve the VRP. It was motivated by the work of Glover regarding surrogate constraints [15]. An important principle behind AMP is that good solutions may be constructed by combining different components of other good solutions. A memory containing components of visited solutions is kept. Periodically, a new solution is constructed using the data in the memory and improved by a local search procedure.

Benchmark problems

The algorithm was tested over the 104 benchmark problems proposed by Taillard et al. [7]. These were constructed using the same graphs, demands and vehicle capacities than the problems 1–5 and 11, 12 proposed by Christofides et al. [14] and problems 11 and 12 proposed by Fisher [28] for the VRP. For each VRP instance, several values of m are used. For each m, two time horizons $T_{1} = [1.05 z^{*} / m]$ and $T_{2} = [1.10 z^{*} / m]$ are proposed, where $z^{*}$ is the best known solution value for the VRP instance and $[a]$

Conclusion and future work

An algorithm based on the Adaptive Memory Programming principle has been proposed to solve the Vehicle Routing Problem (VRP) with Multiple Trips, an important extension of the classic VRP.

The algorithm was ran over a set of benchmark problems and the solutions obtained were compared with those reported for three previously proposed algorithms [7], [9], [11]. Our algorithm obtained more feasible solutions than the previous approaches. Further analysis shows that a good compromise between routing

Acknowledgements

The authors are grateful to the anonymous referees, whose comments helped to improve the presentation of this paper and the quality of the reported results.

References (29)

J. Brandão et al.
A tabu search algorithm for the multi-trip vehicle routing and scheduling problem
European Journal of Operational Research
(1997)
M. Gendreau et al.
A tabu search heuristic for the heterogeneous fleet vehicle routing problem
Computers and Operations Research
(1999)
L. Hvattum et al.
Adaptive memory search for boolean optimization problems
Discrete Applied Mathematics
(2004)
B. Bozkaya et al.
A tabu search heuristic and adaptive memory procedure for political districting
European Journal of Operational Research
(2003)
H. Tang et al.
A TABU search heuristic for the team orienteering problem
Computers and Operations Research
(2005)
S. Ahmadi et al.
Greedy random adaptive memory programming search for the capacitated clustering problem
European Journal of Operational Research
(2005)
E. Taillard et al.
Adaptive memory programming: a unified view of metaheuristics
European Journal of Operational Research
(2001)
Toth P, Vigo D. The vehicle routing problem. SIAM Monographs on Discrete Mathematics and Applications,...
Y. Rochat et al.
Probabilistic diversification and intensification in local search for vehicle routing
Journal of Heuristics
(1995)
J. Lenstra et al.
Complexity of vehicle routing and scheduling problems
Networks
(1981)

Fleischmann B. The vehicle routing problem with multiple use of vehicles. Working paper, Fachbereich...

G. Clarke et al.

Scheduling of vehicles from a central depot to a number of delivery points

Operations Research

(1964)

S. Martello et al.

Knapsack problems

(1990)

E. Taillard et al.

The vehicle routing problem with multiple use of vehicles

Journal of the Operational Research Society

(1996)

Cited by (136)

Home chemotherapy delivery: An integrated production scheduling and multi-trip vehicle routing problem
2024, European Journal of Operational Research
Home chemotherapy systems allow the administration of cancer treatments at a patient’s residence, avoiding an admission to inpatient care facilities. This innovative health care model is interesting both economically and on a human level. It also raises several logistical challenges. This paper focuses on one of the optimization problems arising in the context of home chemotherapy services, where a complex scheduling problem underlies the operational planning process. Indeed, some injectable chemotherapy drugs may remain stable only during a few hours after being produced. Consequently, their production has to be carefully scheduled jointly with their administration, which takes place at the patients homes during a predefined time window. This gives rise to an integrated production scheduling and vehicle routing problem, that we address using a large neighborhood search approach. Production and administration sequences are iteratively modified, while a linear program is used to determine optimal production and administration start times for the candidate sequences. We analyze the impact of the linear program and establish that it is a crucial component of the proposed method. We assess the performance of the proposed method by comparing its solutions with those obtained through a compact mathematical formulation. We then provide insights about the cost of taking into consideration time-related aspects of the problem, i.e., integrated planning horizons, drug stability times, and administration time windows.
Optimization of a rural bus service integrated with e-commerce deliveries guided by a new sustainable policy in China
2023, Transportation Research Part E: Logistics and Transportation Review
Electronic business has expanded, resulting in flourishing rural e-commerce globally, and particularly in China. This paper introduces a novel rural public transit system that integrates passenger and freight services—a rural electric bus service that provides services for passengers and e-commerce packages. This blended service reduces logistical costs and generates additional income for the transit operator. The objective is to minimise cost for the transit user and operator by using a mixed-integer linear programming model that solves bus routing and bus trip scheduling for multiple rural towns; in addition, the model is tested by the Gurobi solver at small-scale instances. The developed solution is a hybrid heuristic algorithm based on adaptive large neighborhood search and tabu search approaches. Finally, a case study in China is conducted to examine the proposed cost-effective methodology and ensure that the integrated scheme will significantly save operational system costs without causing any passenger inconvenience. The research also shows how to optimally design the size of rural electric buses to reduce purchasing and maintenance costs. The optimal results of the case study, comprising 5 towns and 78 villages, show an annual cost saving of approximately ¥847,000 (approximately $121,000) and an annual mileage saving of approximately 66,000 km for the proposed scheme. In addition, the case study explicates key parameters selected for transfer package requirements and the effective deployment of the proposed scheme.
An improved memetic algorithm for integrated production scheduling and vehicle routing decisions
2023, Computers and Operations Research
Motivated by traditional Chinese medicine decoction and delivery problems in our collaborative Chinese medicine decoction company, this study addresses integrated production scheduling and vehicle routing decisions. To deal with this problem, we first propose a mixed integer linear programming model considering hybrid flow shop production and multi-trip multi-vehicle delivery, which is challenging to solve for medium- and large-size instances. We then propose an improved memetic algorithm (MA) that combines a genetic algorithm (GA) with education operators, including local search procedures. To improve the performance of the MA, we consider the contribution of diversity in the fitness function to enhance the exploratory ability, propose a parent selection operator by considering the softmax function to balance exploitation and exploration, and design three customized crossover operators and five education operators with local search procedures. Numerical experiments show that the integrated scheduling method shortens the total makespan by 11.19% compared with separated production scheduling and vehicle routing methods. We compare the proposed MA with Gurobi for small-size instances, and with the GA for special cases (single-stage production) for medium- or large-size instances. The results of numerical experiments for 360 instances show that the MA can find solutions with a gap of no more than 2% from the optimal solution within 3 s for small-size instances, and can improve the solutions of the GA and the adaptive large neighborhood search (ALNS) algorithm by more than 30% and 10%.
Modeling and solving a multi-trip multi-distribution center vehicle routing problem with lower-bound capacity constraints
2022, Computers and Industrial Engineering
Vehicle routing problem (VRP) for delivering goods from distribution centers to customers is one of the main operations in logistics. Optimizing route plans for vehicles allows companies to save a huge amount of operational costs. The VRP problem is also one of the most studied problems in the domain of operations research. There are several variants of the VRP problem that have been considered in the literature. This paper proposes a new variant of the vehicle routing problem taking into account most of the well-studied features, especially with a new constraint on the lower bound of the capacity of vehicles which has not been investigated in the literature. The problem requirements come from one of the biggest dairy distribution companies in Vietnam. With over 1000 customer points included in a plan on average, the company takes at least one working day to make a route plan. We formulate the considered problem as a mixed-integer linear programming problem, analyze the challenges of the lower-bound capacity constraints and propose an adaptive large neighborhood search framework for solving it. Experimental results on large realistic and randomly generated instances show the efficiency and the applicability of the proposed method. The application of the proposed method led to the rapidity in generating the solution; this task that used to take one day is decreased to just two hours.
A multi-trip electric bus routing model considering equity during short-notice evacuations
2022, Transportation Research Part D: Transport and Environment
Widespread use of electric vehicles (EVs) and electric buses (EBs) adds new challenges to short-notice evacuations. Studies modeling EV behavior suggest that the power grid in most cases cannot handle EV demand during the evacuation preparation stage, but ignore the potential efficiencies of coordinated EBs. To overcome this shortcoming, a generalized framework based on three multi-trip EB routing models is developed to a) estimate the feasibility of using EBs during short-notice evacuations by examining evacuation efficiency, b) analyze EB charging behavior considering evacuation efficiency and path assignment equity, and c) explore the economic advantages of using EBs by comparing EBs with conventional liquefied natural gas (LNG) buses in terms of efficiency and operational cost. A genetic algorithm with an improved recombination strategy (GA-IR) is developed to solve these models. Computational results show that GA-IR outperforms GA in terms of convergence speed and solution quality, as GA-IR takes into account the empty trip removal process and the charging station re-insertion process, which is an innovation of GA-IR. Sensitivity analysis shows that using k-means clustering to position charging stations, and increasing the number of charging stations and EBs can improve evacuation efficiency.
Adaptive large neighborhood search for vehicle routing problems with transshipment facilities arising in city logistics
2022, Computers and Operations Research
In this paper, we investigate vehicle routing problems with third-party transshipment facilities that arise in the context of city logistics. Contrary to classical vehicle routing problems, where each customer request is delivered directly to its destination, the problems considered in this paper feature the alternative possibility of delivering customer requests to third-party transshipment facilities, such as urban consolidation centers, for a fee. We present an adaptive large neighborhood search with an embedded random variable neighborhood descent as a local search component and a set-partitioning problem for the recombination of routes to solve various versions of the problem. Thereby, we consider location-dependent time windows as well as heterogeneous fleets and propose several new procedures that consider transshipment facilities within the components of our adaptive large neighborhood search. The proposed method is tested on benchmark instances from the literature as well as newly created benchmark instances. It shows promising results, leading to multiple improvements over existing algorithms from the literature. Moreover, a real-world study is presented to gain managerial insights on the impact of transshipment fees, order size, and heterogeneous fleets on the transshipment decisions.

View all citing articles on Scopus

View full text

Adaptive memory programming for the vehicle routing problem with multiple trips

Abstract

Introduction

Section snippets

The VRP with multiple trips

Adaptive memory algorithm

Benchmark problems

Conclusion and future work

Acknowledgements

European Journal of Operational Research

Computers and Operations Research

Discrete Applied Mathematics

European Journal of Operational Research

Computers and Operations Research

European Journal of Operational Research

European Journal of Operational Research

Probabilistic diversification and intensification in local search for vehicle routing

Journal of Heuristics

Complexity of vehicle routing and scheduling problems

Networks

Scheduling of vehicles from a central depot to a number of delivery points

Operations Research

Knapsack problems

The vehicle routing problem with multiple use of vehicles

Journal of the Operational Research Society