×
Sexton, Thomas R.; Choi, Young-Myung

Pickup and delivery of partial loads with “soft” time windows. (English) Zbl 0633.90029

Am. J. Math. Manage. Sci. 6, 369-398 (1986).
We apply Benders’ decomposition procedure to the single-vehicle routing and scheduling problem with time windows, partial loads, and dwell times. We provide a formula and demonstrate that the scheduling subproblem is the dual of a network flow problem. We describe an exact algorithm which exploits its structure, and construct a route improvement heuristic based on the master problem. A heuristic for building an initial route is also presented.

Cited in 23 Documents

MSC:

90B35 Deterministic scheduling theory in operations research

Keywords:

Benders’ decomposition; single-vehicle routing; time windows; partial loads; dwell times; network flow; route improvement heuristic
Cite Review PDF
Full Text: DOI

References:

[1] Armstrong G.R., Dynamic programming solution of the single and multiple vehicle pickup and delivery problem with application to Dial-A-Ride (1982)
[2] Assad A., Proceedings of the 1981 Northeast AIDS Conference pp 99– (1981)
[3] Ball M., Decision Sciences 14 pp 103– (1983) · doi:10.1111/j.1540-5915.1983.tb00172.x
[4] Benders J.F., Numerische Mathematik 4 pp 238– (1962) · Zbl 0109.38302 · doi:10.1007/BF01386316
[5] Bodin L., Networks 11 pp 97– (1981) · doi:10.1002/net.3230110204
[6] Bodin L., Computers and Operations Research 10 pp 63– (1983) · doi:10.1016/0305-0548(83)90030-8
[7] Bodin L., The Delivery of Urban Services, TIMS Studies in the Management Sciences pp 22–
[8] Busacker R.G., Finite Graphs and Networks: An Introduction with Applications. (1965) · Zbl 0146.20104
[9] Choi Y.-M., The single vehicle trailer routing and scheduling problem with partial loads, time windows and dwell times (1984)
[10] Cullen F.H., Networks 11 pp 125– (1981) · doi:10.1002/net.3230110206
[11] Fisher M.L., Networks 11 pp 109– (1981) · doi:10.1002/net.3230110205
[12] Ford L.R., Flows in Networks (1962) · Zbl 0106.34802
[13] Klein M., Management Science 14 pp 205– (1967) · Zbl 0178.22902 · doi:10.1287/mnsc.14.3.205
[14] Lenstra J., Networks 11 pp 221– (1981) · doi:10.1002/net.3230110211
[15] Love R.R., Mathematical Programming Study 15 pp 102– (1981) · Zbl 0477.90029 · doi:10.1007/BFb0120940
[16] Magnanti T.L., Networks 11 pp 179– (1981) · doi:10.1002/net.3230110209
[17] Psaraftis H.N., Transportation Science 14 pp 130– (1980) · doi:10.1287/trsc.14.2.130
[18] Psaraftis H.N., Transportation Science 17 pp 351– (1983) · doi:10.1287/trsc.17.3.351
[19] Sexton T.R., The single vehicle many-to-many routing and scheduling problem (1979)
[20] Sexton T.R., The single vehicle many-to-many routing and scheduling problem with customer-dependent dwell times (1981)
[21] Sexton T.R., Transportation Science 19 pp 378– (1985) · Zbl 0608.90043 · doi:10.1287/trsc.19.4.378
[22] Sexton T.R., Transportation Science 19 pp 411– (1985) · Zbl 0618.90042 · doi:10.1287/trsc.19.4.411
[23] Solomon M.M., Vehicle routing and scheduling with time window constraints: Models and algorithms (1978)
[24] Stein D.M., Transportation Science 12 pp 232– (1978) · doi:10.1287/trsc.12.3.232
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.