Heuristics for vehicle routing on tree-like networks
- PDF / 170,250 Bytes
- 9 Pages / 595 x 842 pts (A4) Page_size
- 41 Downloads / 192 Views
#1999 Operational Research Society Ltd. All rights reserved. 0160-5682/99 $12.00 http://www.stockton-press.co.uk/jor
Heuristics for vehicle routing on tree-like networks C Basnet1, LR Foulds1 and JM Wilson2 1
University of Waikato, New Zealand and 2Loughborough University, UK
This paper presents two new heuristics for the vehicle routing problem on tree-like road networks. These networks occur, for example, in rural road systems where the supply (or delivery) nodes are located on rural roads leading off from a few highways which form the `trunks' of a tree-like network. The heuristics have the conventional objective of minimising the total distance travelled by the vehicles. The development of the heuristics takes advantage of the tree-like structure of the network. These two new heuristics and two other heuristics from the published literature are applied to some test problems and computational results are presented. The computational experience indicates that one of the new heuristics provides superior solutions to the existing heuristics and in reasonable computing time. It therefore appears suitable for large-scale practical routing problems. Keywords: vehicle routing; tree network; heuristics; savings approach
Introduction The Capacitated Vehicle Routing Problem (CVRP) is one of the classical areas of study in operational research. CVRP and its related problems have been studied extensively (see, for example: Turner et al,1 Watson-Gandy and Foulds,2 Basnet et al,3 Laporte and Nobert,4 and Golden and Assad5). The standard capacitated vehicle routing problem assumes that each node in the underlying transportation network is directly connected to many other nodes. This assumption is not always valid, for example, some rural delivery networks consist of roads that branch off from a single highway. Therefore there is only one possible route from any one node to another node. In graph theoretic terms (Foulds6) these networks are called trees, and this paper is concerned with the problem of vehicle routing on trees (TCVRP). The TCVRP is a special case of the classical CVRP. Only the network is different in TCVRP, other features of the problem remain the same: 1. Vehicle routes start and end in a node called the depot (designated as root of the tree). 2. Each node has a demand which is serviced by a single vehicle. 3. The total demand serviced by a vehicle cannot exceed its capacity Q, which is common to all the vehicles. 4. The objective is to ®nd the routes for the vehicles that will minimise the total distance travelled. The problem of capacitated vehicle routing on trees (TCVRP) has been studied by Labbe et al.7 They show Correspondence: Dr C Basnet, Department of Management Systems, University of Waikato, Private Bag 3105, Hamilton 2020, New Zealand. E-mail: [email protected]
that the TCVRP is NP-hard. This underscores the search for ef®cient heuristics to address this problem. This paper presents two new heuristics for the problem, and compares these heuristics to two others from extant literature. The re
Data Loading...
