The probabilistic traveling salesman problem with time windows
- PDF / 614,118 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 118 Downloads / 225 Views
The probabilistic traveling salesman problem with time windows Stacy A. Voccia • Ann M. Campbell Barrett W. Thomas
•
Received: 30 July 2012 / Accepted: 16 January 2013 / Published online: 14 February 2013 Ó Springer-Verlag Berlin Heidelberg and EURO - The Association of European Operational Research Societies 2013
Abstract With time-definite services occupying a large part of the delivery business, the explicit consideration of time windows into a route design has the potential to reduce transportation costs and the penalty costs associated with late deliveries. In this paper, we incorporate time windows into a priori routes by introducing the probabilistic traveling salesman problem with time windows (PTSPTW). The PTSPTW is an extension of the well-known probabilistic traveling salesman problem, where in addition to stochastic customer presence, each customer has an associated time window during which deliveries must be made. We present a recourse model and a variable neighborhood search with variable neighborhood descent algorithm to solve problem instances. We also present computational experiments that demonstrate the value of incorporating stochasticity into the problem. Keywords
Traveling salesman problem Probabilistic Time windows
Electronic supplementary material The online version of this article (doi:10.1007/s13676-013-0018-0) contains supplementary material, which is available to authorized users. S. A. Voccia A. M. Campbell (&) B. W. Thomas Department Of Management Sciences, University Of Iowa, 108 John Pappajohn Business Building, Iowa City, IA 52242-1994, USA e-mail: [email protected] S. A. Voccia e-mail: [email protected] B. W. Thomas e-mail: [email protected]
123
90
S. A.Voccia et al.
Introduction Time-definite delivery plays a crucial role in the shipping industry. Now more than ever, businesses are operating with lean production strategies and just-in-time inventories. With this trend, freight is shipped in smaller lot sizes and the predictability of arrival times is critical (Schultz 2008). Randy Guidry, communications coordinator for Averitt Express, notes ‘‘Every year, more and more of our customers are requesting appointments within a delivery window’’ (Terreri 2011). In 2010, time-definite, day definite and same day delivery services accounted for 51.4 % of the United States shipping industry’s total market value (Datamonitor 2010b). In the European market, these segments accounted for 62.3 % in 2010, a 10.6 % increase from 2009 (Datamonitor 2010a, 2009). With time-definite services occupying a large part of the delivery business, the explicit consideration of time windows into a route design has the potential to reduce transportation costs and the penalty costs associated with late deliveries. Currently, many companies employ a pre-planned, or a priori, route which identifies an ordering of all possible customers that a particular driver may need to visit. The driver then skips those customers on the route who do not require a delivery on that day. A priori r
Data Loading...
