Mathematical Problems in Engineering
Volume 2008 (2008), Article ID 697981, 17 pages
doi:10.1155/2008/697981
Research Article
Single-Commodity Vehicle Routing Problem with Pickup and Delivery Service
Faculty of Electrical Engineering, Josip Juraj Strossmayer University of Osijek, Kneza Trpimira 2b, 31000 Osijek, Croatia
Received 24 May 2008; Revised 6 October 2008; Accepted 19 December 2008
Academic Editor: Alois Steindl
Copyright © 2008 Goran Martinovic et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
We present a novel variation of the vehicle routing problem (VRP). Single commodity cargo with pickup and delivery service is considered. Customers are labeled as either cargo sink or cargo source, depending on their pickup or delivery demand. This problem is called a single commodity vehicle routing problem with pickup and delivery service (1-VRPPD). 1-VRPPD deals with multiple vehicles and is the same as the
single-commodity traveling salesman problem (1-PDTSP) when the number of vehicles is equal to 1.
Since 1-VRPPD specializes VRP, it is 𝒩𝒫 hard in the strong sense. Iterative modified simulated annealing (IMSA) is presented along with greedy random-based initial solution algorithm. IMSA provides a good approximation to the global optimum in a large search space. Experiment is done for the instances with different number of customers and their demands. With respect to average values of IMSA execution times, proposed method is appropriate for practical applications.