A Simulated Annealing Algorithm for the Vehicle Routing Problem with Time Windows and Synchronization Constraints
This paper focuses on solving a variant of the vehicle routing problem (VRP) in which a time window is associated with each customer service and some services require simultaneous visits from different vehicles to be accomplished. The problem is therefore
- PDF / 179,802 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 81 Downloads / 199 Views
1 Universit´e de Technologie de Compi`egne, Laboratoire Heudiasyc, UMR 7253 CNRS, Compi`egne 60205, France School of Computer Science, ASAP Research Group, University of Nottingham, Jubilee Campus, Wollaton Road, Nottingham NG8 1BB, UK {sohaib.afifi,duc-cuong.dang,aziz.moukrim}@hds.utc.fr
Abstract. This paper focuses on solving a variant of the vehicle routing problem (VRP) in which a time window is associated with each customer service and some services require simultaneous visits from different vehicles to be accomplished. The problem is therefore called the VRP with time windows and synchronization constraints (VRPTWSyn). We present a simulated annealing algorithm (SA) that incorporates several local search techniques to deal with this problem. Experiments on the instances from the literature show that our SA is fast and outperforms the existing approaches. To the best of our knowledge, this is the first time that dedicated local search methods have been proposed and evaluated on this variant of VRP.
Keywords: Vehicle routing Simulated annealing
1
·
Synchronization
·
Destruction/repair
·
Introduction
The vehicle routing problem (VRP) [9] is a widely studied combinatorial optimization problem in which the aim is to design optimal tours for a set of vehicles serving a set of customers geographically distributed and respecting some side constraints. We are interested in a particular variant of VRP, the so-called VRP with time windows and synchronization constraints (VRPTWSyn). In such a problem, each customer is associated with a time window that represents the interval of time when the customer is available to receive the vehicle service. This means that if the vehicle arrives too soon, it should wait until the opening of the time window to serve the customer while too late arrival is not allowed. Additionally, for some customers, more than one visit, e.g. two visits from two This work is partially supported by the Regional Council of Picardie and the European Regional Development Fund (ERDF), under PRIMA project.
G. Nicosia and P. Pardalos (Eds.): LION 7, LNCS 7997, pp. 259–265, 2013. c Springer-Verlag Berlin Heidelberg 2013 DOI: 10.1007/978-3-642-44973-4 27,
260
S. Afifi et al.
different vehicles, are required to complete the service. Visits associated to a particular customer need to be synchronized, e.g. having the same start time. VRPTWSyn was first studied in [3] with an application in health care services for elders. In such services, the timing and coordination are crucial and therefore the temporal constraints. The readers are referred to [4] for a complete review of those constraints involved in vehicle routing. As an extension of VRP, VRPTWSyn is clearly NP-Hard. There are only a few attempts to solve this problem in the literature [2,3]. In those works, even heuristic ones, integer linear programming is the key ingredient and the methods often require much computational time to deal with large instances. Motivated by the potential applications and by the challenge of computational time, i
Data Loading...
