Title: Generalised pickup and delivery problem with dynamic time windows

Authors: N. Chanaka P. Edirisinghe, Melissa R. Bowers, Anurag Agarwal

Addresses: Department of Statistics, Operations and Management Science, College of Business Administration, The University of Tennessee, Knoxville, TN 37996, USA. ' Department of Statistics, Operations and Management Science, College of Business Administration, The University of Tennessee, Knoxville, TN 37996, USA. ' Risk Management Solutions, Inc., 250 Harry Lane Blvd Ste B, Knoxville, TN 37923, USA

Abstract: This paper considers the general class of vehicle routing problems in which nodes may be visited multiple times by multiple vehicles. The vehicles must pickup a product under continuous production at nodes and deliver it to a central depot. The nodes must be visited within certain time windows which are dependent on product availability at the nodes and the routes taken by vehicles, hence, the term, dynamic time windows. A model formulation is proposed using mixed-integer programming, along with two different performance metrics for tour optimisation: total product delivery at the depot, and another associated with rate of product delivery. The MIPs with non-linear objective functions are solved through a new convergent iterative algorithm in which sequences of parametric mixed-integer linear programmes are solved. The model is applied to a real-world situation that involves scheduling barges for oil pickup from offshore oil platforms. Preliminary computational results are presented.

Keywords: barge scheduling; dynamic time windows; nonlinear mixed-integer programming; vehicle routing model; oil pickup; offshore oil platforms.

DOI: 10.1504/IJOR.2010.033105

International Journal of Operational Research, 2010 Vol.8 No.1, pp.85 - 109

Published online: 08 May 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article