×

Exact and heuristic dynamic programming algorithms for the traveling salesman problem with flexible time windows. (English) Zbl 1442.90164

Summary: This article proposes extensions of exact and heuristic dynamic programming algorithms for the traveling salesman problem with flexible time windows, which are a limited enlargement of the generally referred to as hard time windows. The service of a customer can be started before or after the hard time window at a penalty cost. The addressed problem thus requires the determination of a sequence of customers and their respective service start times in order to minimize the sum of traveling cost with earliness and lateness cost. Computational tests are conducted on a variety of symmetric and asymmetric instances proposed in the literature, and the advantages of flexible windows are stressed.

MSC:

90C27 Combinatorial optimization
90C39 Dynamic programming

Software:

TSPLIB; VRP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, R.; Magnanti, T.; Orlin, J., Network Flows: Theory, Algorithms, and Applications (1993), Upper Saddle River, NJ: Prentice Hall, Upper Saddle River, NJ · Zbl 1201.90001
[2] Balakrishnan, N., Simple heuristics for the vehicle routeing problem with soft time windows, J. Oper. Res. Soc., 44, 3, 279-287 (1993) · Zbl 0771.90033 · doi:10.1057/jors.1993.53
[3] Balas, E., New classes of efficiently solvable generalized traveling salesman problems, Ann. Oper. Res., 86, 529-558 (1999) · Zbl 0922.90138 · doi:10.1023/A:1018939709890
[4] Balas, E.; Simonetti, N., Linear time dynamic-programming algorithms for new classes of restricted TSPs: a computational study, INFORMS J. Comput., 13, 1, 56-75 (2001) · Zbl 1238.90126 · doi:10.1287/ijoc.13.1.56.9748
[5] Balas, E.; Simonetti, N.; Vazacopoulos, A., Job shop scheduling with setup times, deadlines and precedence constraints, J. Sched., 11, 4, 253-262 (2008) · Zbl 1168.90419 · doi:10.1007/s10951-008-0067-7
[6] Baldacci, R.; Mingozzi, A.; Roberti, R., New state-space relaxations for solving the traveling salesman problem with time windows, INFORMS J. Comput., 24, 3, 356-371 (2012) · Zbl 1462.90102 · doi:10.1287/ijoc.1110.0456
[7] Bellman, R., Dynamic Programming (1957), Upper Saddle River, NJ: Princeton University Press, Upper Saddle River, NJ · Zbl 0077.13605
[8] Bhusiri, N.; Qureshi, AG; Taniguchi, E., The trade-off between fixed vehicle costs and time-dependent arrival penalties in a routing problem, Transp. Res. Part E Log., 62, 1-22 (2014) · doi:10.1016/j.tre.2013.12.003
[9] Chiang, WC; Russell, RA, A metaheuristic for the vehicle routeing-problem with soft time windows, J. Oper. Res. Soc., 55, 12, 1298-1310 (2004) · Zbl 1088.90019 · doi:10.1057/palgrave.jors.2601791
[10] Denardo, EV, Dynamic Programming: Models and Applications (1982), Upper Saddle River, NJ: Prentice Hall, Upper Saddle River, NJ
[11] Desaulniers, G.; Lessard, F.; Hadjar, A., Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows, Transp. Sci., 42, 3, 387-404 (2008) · doi:10.1287/trsc.1070.0223
[12] Desrochers, M.: An algorithm for the shortest path problem with resource constraints. Technical report G-88-27, GERAD, Montreal (1988) · Zbl 0677.90080
[13] Desrosiers, J.; Dumas, Y.; Solomon, MM; Soumis, F.; Ball, MO; Magnanti, TL; Monma, CL; Nemhauser, FL, Time constrained routing and scheduling, Handbooks in Operations Research and Management Science, 35-139 (1995), Amsterdam: Elsevier, Amsterdam · Zbl 0861.90052
[14] Dumas, Y.; Desrosiers, J.; Gelinas, E.; Solomon, MM, An optimal algorithm for the traveling salesman problem with time windows, Oper. Res., 43, 2, 367-371 (1995) · Zbl 0837.90036 · doi:10.1287/opre.43.2.367
[15] Dumas, Y.; Soumis, F.; Desrosiers, J., Optimizing the schedule for a fixed vehicle path with convex inconvenience costs, Transp. Sci., 24, 145-152 (1990) · Zbl 0715.90066 · doi:10.1287/trsc.24.2.145
[16] Feillet, D.; Dejax, P.; Gendreau, M.; Gueguen, C., An exact algorithm for the elementary shortest path problem with resource constraints: application to some vehicle routing problems, Networks, 44, 3, 216-229 (2004) · Zbl 1056.90014 · doi:10.1002/net.20033
[17] Fischetti, M.; Toth, P., A polyhedral approach to the asymmetric traveling salesman problem, Manag. Sci., 43, 11, 1520-1536 (1997) · Zbl 0902.90159 · doi:10.1287/mnsc.43.11.1520
[18] Fischetti, M.; Toth, P.; Vigo, D., A branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs, Oper. Res., 42, 5, 846-859 (1994) · Zbl 0815.90065 · doi:10.1287/opre.42.5.846
[19] Fleischmann, B., The discrete lot-sizing and scheduling problem with sequence-dependent setup costs, Eur. J. Oper. Res., 75, 2, 395-404 (1994) · Zbl 0804.90070 · doi:10.1016/0377-2217(94)90083-3
[20] Fry, TD; Leong, GK, Single machine scheduling: a comparison of two solution procedures, OMEGA Int. J. Manag. Sci., 15, 4, 277-282 (1987) · doi:10.1016/0305-0483(87)90015-6
[21] Golden, BL; Stewart, WR; Lawler, EL; Lenstra, JK; Rinnooy Kan, AHG; Shmoys, DB, Empirical analysis of heuristics, The traveling salesman problem, 207-250 (1985), Chichester: Wiley, Chichester · Zbl 0591.90090
[22] Ibaraki, T.; Imahori, S.; Kubo, M.; Masuda, T.; Uno, T.; Yagiura, M., Effective local search algorithms for routing and scheduling problems with general time window constraints, Transp. Sci., 39, 2, 206-232 (2005) · doi:10.1287/trsc.1030.0085
[23] Kohl, N.; Desrosiers, J.; Madsen, OBG; Solomon, MM; Soumis, F., 2-path cuts for the vehicle routing problem with time windows, Transp. Sci., 33, 1, 101-116 (1999) · Zbl 1004.90015 · doi:10.1287/trsc.33.1.101
[24] Koskosidis, YA; Powell, WB; Solomon, MM, An optimization based heuristic for vehicle routeing and scheduling with soft time window constraints, Transp. Sci., 26, 69-85 (1992) · Zbl 0762.90022 · doi:10.1287/trsc.26.2.69
[25] Li, J.Q.: A computational study of bi-directional dynamic programming for the traveling salesman problem with time windows. Working paper, University of California, Berkeley (2009)
[26] Liberatore, F.; Righini, G.; Salani, M., A column generation algorithm for the vehicle routing problem with soft time windows, 4OR. Q. J. Oper. Res., 9, 1, 49-82 (2011) · Zbl 1225.90110 · doi:10.1007/s10288-010-0136-6
[27] Qureshi, A.; Taniguchi, E.; Yamada, T., An exact solution approach for vehicle routing and scheduling problems with soft time windows, Transp. Res. Part E Log., 45, 6, 960-977 (2009) · doi:10.1016/j.tre.2009.04.007
[28] Reinelt, G., TSPLIB—a traveling salesman problem library, ORSA J. Comput., 3, 4, 376-384 (1991) · Zbl 0775.90293 · doi:10.1287/ijoc.3.4.376
[29] Righini, G.; Salani, M., Symmetry helps: bounded bidirectional dynamic programming for the elementary shortest path problem with resource constraints, Discrete Optim., 3, 3, 255-273 (2006) · Zbl 1149.90167 · doi:10.1016/j.disopt.2006.05.007
[30] Savelsbergh, MWP, Local search in routing problems with time windows, Ann. Oper. Res., 4, 1, 285-305 (1985) · doi:10.1007/BF02022044
[31] Sexton, TR; Bodin, LD, Optimizing single vehicle many-to-many operations with desired delivery times: I, Sched. Transp. Sci., 19, 4, 378-410 (1985) · Zbl 0608.90043 · doi:10.1287/trsc.19.4.378
[32] Sexton, TR; Choi, Y., Pickup and delivery of partial loads with soft time windows, Am. J. Math. Soc., 6, 369-398 (1986) · Zbl 0633.90029
[33] Taillard, E.; Badeau, P.; Gendreau, M.; Guertin, F.; Potvin, JY, A tabu search heuristic for the vehicle routing problem with soft time windows, Transp. Sci., 31, 2, 170-186 (1997) · Zbl 0886.90070 · doi:10.1287/trsc.31.2.170
[34] Taş, D.; Jabali, O.; Woensel, TV, A vehicle routing problem with flexible time windows, Comput. Oper. Res., 52, 39-54 (2014) · Zbl 1348.90136 · doi:10.1016/j.cor.2014.07.005
[35] Vidal, T.; Crainic, TG; Gendreau, M.; Prins, C., Timing problems and algorithms: time decisions for sequences of activities, Networks, 65, 2, 102-128 (2015) · Zbl 1390.90486 · doi:10.1002/net.21587
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.