×

Selecting good a priori sequences for vehicle routing problem with stochastic demand. (English) Zbl 1351.90022

Cerone, Antonio (ed.) et al., Theoretical aspects of computing – ICTAC 2011. 8th international colloquium, Johannesburg, South Africa, August 31 – September 2, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-23282-4/pbk). Lecture Notes in Computer Science 6916, 45-61 (2011).
Summary: In the vehicle routing problem with stochastic demand, the customers’ demands vary from one collection/delivery period to the next. Under the assumption that they become known only upon arrival of the vehicle at their sites, our objective is to find a fixed a priori sequence that is used in every period. We present a priori sequences that achieve 2-, 2-, 3- and 5-approximation in the worst case on trees, cycles, cactus graphs, and general graphs, respectively, in the case where the demand of a customer must be serviced all at once. These approximation ratios are with respect to the optimal distance computed off-line, when all demands are non-zero and are known in advance. If the demand of a customer can be serviced in parts, we present a linear time algorithm to find an optimal solution for cycles.
For the entire collection see [Zbl 1229.68001].

MSC:

90B06 Transportation, logistics and supply chain management
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Altinkemer, K., Gavish, B.: Heuristics for unequal weight delivery problems with a fixed error guarantee. Operations Research Letters 6(4), 149–158 (1987) · Zbl 0632.90083 · doi:10.1016/0167-6377(87)90012-5
[2] Asano, T., Katoh, N., Kawashima, K.: A new approximation algorithm for the capacitated vehicle routing problem on a tree. J. of Combinatorial Optimization 5(2), 213–231 (2004) · Zbl 1039.90007 · doi:10.1023/A:1011461300596
[3] Berman, P., Das, S.K.: On the vehicle routing problem. In: Proc. Workshop on Algorithms and Data Structures, pp. 360–371 (2005) · Zbl 1161.68873 · doi:10.1007/11534273_32
[4] Bertsimas, D.J.: A vehicle routing problem with stochastic demand. Operations Research 40(3), 574–585 (1992) · Zbl 0764.90030 · doi:10.1287/opre.40.3.574
[5] Bertsimas, D.J., Simchi-Levi, D.: A new generation of vehicle routing research: Robust algorithms, addressing uncertainty. Operations Research 44, 216–304 (1996) · Zbl 0855.90053 · doi:10.1287/opre.44.2.286
[6] Charikar, M., Khuller, S., Raghavachari, B.: Algorithms for capacitated vehicle routing. SIAM J. on Computing 31(3), 665–682 (2002) · Zbl 1009.90095 · doi:10.1137/S0097539701392056
[7] Charikar, M., Raghavachari, B.: The finite capacity Dial-a-Ride problem. In: Proc. 39th Annual Symp. on Foundations of Computer Science, pp. 458–467 (1998) · doi:10.1109/SFCS.1998.743496
[8] Christofides, N.: The traveling salesman problem. In: Christofides, N., Mingozzi, A., Toth, P., Sandi, C. (eds.) Combinatorial Optimization, pp. 315–318 (1979)
[9] Dror, M., Laporte, G., Trudeau, P.: Vehicle routing with stochastic demands: Properties and solution frameworks. Transportation Science 23(3), 166–176 (1989) · Zbl 0689.90025 · doi:10.1287/trsc.23.3.166
[10] Dror, M., Ball, M., Golden, B.: A computational comparison of algorithms for the inventory routing problem. Annals of Operations Research 6, 3–23 (1985)
[11] Golden, B.L., Raghavan, S., Wasil, E.A. (eds.): The Vehicle Routing Problem: Latest Advances and New Challenges. Operations Research Computer Science Interfaces Series, vol. 43. Springer, Heidelberg (2008) · Zbl 1142.90004
[12] Haimovich, A., Kan, A.R.: Bounds and heuristics for capacitated routing problems. Mathematics of Operations Research 10, 527–542 (1985) · Zbl 0582.90030 · doi:10.1287/moor.10.4.527
[13] Hamaguchi, S.-y., Katoh, N.: A capacitated vehicle routing problem on a tree. In: Chwa, K.-Y., Ibarra, O.H. (eds.) ISAAC 1998. LNCS, vol. 1533, pp. 397–406. Springer, Heidelberg (1998) · Zbl 0922.90057 · doi:10.1007/3-540-49381-6_42
[14] Jaillet, P., Odoni, A.: The probabilistic vehicle routing problem. In: Golden, B.L., Assad, A.A. (eds.) Vehicle Routing: Methods and Studies. North Holland, Amsterdam (1988) · Zbl 0653.90032
[15] Kenyon, A., Morton, D.P.: A survey on stochastic location and routing problems. Central European J. of Operations Research 9, 277–328 (2002) · Zbl 1036.90044
[16] Labbé, M., Laporte, G., Mercure, H.: Capacitated vehicle routing on trees. Operations Research 39(4), 616–622 (1991) · Zbl 0736.90029 · doi:10.1287/opre.39.4.616
[17] Marković, L., Ćavar, I., Carić, T.: Using data mining to forecast uncertain demands in stochastic vehicle routing problem. In: Proc. 13th Intn’l Symp. on Electronics in Transport (ISEP), Slovenia, pp. 1–6 (2005)
[18] Novoa, C.: Static and dynamic approaches for solving the vehicle routing problem with stochastic demands. Ph.D. dissertation, Industrial and Systems Engineering Dept., Lehigh University (2005)
[19] Tillman, F.: The multiple terminal delivery problem with probabilistic demands. Transportation Science 3, 192–204 (1969) · doi:10.1287/trsc.3.3.192
[20] Viswanath, N.: Approximation Algorithms for Sequencing Problems. Ph.D. dissertation, Tepper School of Business, Carnegie Mellon University University (2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.