The dynamic nearest neighbor policy for the multi-vehicle pick-up and delivery problem

Sheridan, Patricia Kristine and Gluck, Erich and Guan, Qi and Pickles, Thomas and Balcıoğlu, Ahmet Barış and Benhabib, Beno (2013) The dynamic nearest neighbor policy for the multi-vehicle pick-up and delivery problem. Transportation Research Part A: Policy and Practice, 49 . pp. 178-194. ISSN 0965-8564 (Print) 1879-2375 (Online)

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dx.doi.org/10.1016/j.tra.2013.01.032


In this paper, a dynamic nearest neighbor (DNN) policy is proposed for operating a fleet of vehicles to serve customers, who place calls in a Euclidean service area according to a Poisson process. Each vehicle serves one customer at a time, who has a distinct origin and destination independently and uniformly distributed within the service area. The new DNN policy is a refined version of the nearest neighbor (NN) policy that is well known to perform sub-optimally when the frequency of customer requests is high. The DNN policy maintains geographically closest customer-to-vehicle assignments, due to its ability to divert/re-assign vehicles that may be already en-route to pick up other customers, when another vehicle becomes available or a new customer call arrives. Two other pertinent issues addressed include: the pro-active deployment of the vehicles by anticipating in which regions of the service area future calls are more likely to arise; and, imposition of limits to avoid prohibitively long customer wait times. The paper also presents accurate approximations for all the policies compared. Extensive simulations, some of which are included herein, clearly show the DNN policy to be tangibly superior to the first-comefirst-served (FCFS) and NN policies.

Item Type:Article
Uncontrolled Keywords:Dynamic vehicle routing; Queueing; Anticipatory behavior
Subjects:Q Science > Q Science (General)
ID Code:21462
Deposited By:Barış Balcıoğlu
Deposited On:07 Mar 2013 16:17
Last Modified:01 Aug 2019 10:14

Repository Staff Only: item control page