A multi-start evolutionary local search for the one-commodity pickup and delivery traveling salesman problem
- PDF / 731,479 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 81 Downloads / 166 Views
A multi-start evolutionary local search for the one-commodity pickup and delivery traveling salesman problem Juan D. Palacio1
· Juan Carlos Rivera1
Accepted: 9 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This article addresses the one-commodity pickup and delivery traveling salesman problem (1-PDTSP), which is a generalization of the well-known traveling salesman problem. The 1-PDTSP aims to find a Hamiltonian tour in which a set of supply points (pickup locations), demand points (delivery locations) are visited and, the total traveled distance is minimized. We propose a hybrid metaheuristic based on multi-start evolutionary local search and variable neighborhood descent to solve the 1-PDTSP. To test the performance of our algorithm, we solve instances with up to 500 nodes available in the literature and we demonstrate that our approach is able to provide competitive results when comparing to other existing strategies. Since a direct application of the 1-PDTSP arises as the bicycle repositioning problem, we also use our metaheuristic algorithm to solve a set of real-case instances based on EnCicla, the bicycle sharing system in the Aburrá Valley (Antioquia, Colombia). Keywords Pickup and delivery traveling salesman problem · Evolutionary local search · Variable neighborhood descent · Bicycle repositioning problem
1 Introduction In the one-commodity pickup and delivery traveling salesman problem (1-PDTSP) a set of locations and a capacitated vehicle are given. The locations are classified as supply points (pickup locations) and demand points (delivery locations). One commodity is transported between the locations using the available vehicle. Each supply point provides a certain amount of the commodity and these units can be delivered to one or several demand points (Hernández-Pérez and Salazar-González 2004b). Additionally, one of these locations is set as a depot where the vehicle starts and ends the tour. Thus, the 1-PDTSP aims to find a
B
Juan D. Palacio [email protected] Juan Carlos Rivera [email protected]
1
Mathematical Modeling Research Group. Mathematical Sciences Department, School of Sciences, Universidad EAFIT, Medellín, Colombia
123
Annals of Operations Research
Hamiltonian tour in which the total traveled distance is minimized and the vehicle capacity is satisfied. Moreover, an initial load must be determined for the vehicle. A well-known application for the 1-PDTSP relies on the operation of bicycle sharing systems (BSSs). A BSS is mainly composed by a set of stations with limited capacity (i.e., number of bike slots) distributed along an urban area and also, a set of available bicycles for users. Citizens can use the system by taking a bike from one of the available stations (origin) and then, after a short trip, returning it to the same or a different station (destination). A successful operation of a BSS requires an adequate number of available bikes and parking slots at each station in such a way that the demand is satisfied and t
Data Loading...
