A worst-case analysis for the split delivery capacitated team orienteering problem with minimum delivery amounts
Tóm tắt
In the capacitated team orienteering problem, a fleet of vehicles visits and services a subset of customers in order to maximize the total profit collected while obeying capacity and route length constraints. In the split delivery team orienteering problem (SDCTOP), multiple vehicles can service the same customer; each vehicle satisfies some, but not all, of the customer demand. Allowing split deliveries may double the total profit, in the extreme case. However, split deliveries often cause inconvenience to the customers, so we introduce the split delivery team orienteering problem with minimum delivery amounts (SDCTOP–MDA). In this paper, we perform a worst-case analysis on the SDCTOP–MDA to determine tight bounds on the maximum possible profit increase.
Tài liệu tham khảo
Archetti, C., Bianchessi, N., Speranza, M.G., Hertz, A.: The split delivery capacitated team orienteering problem. Networks 63(1), 16–33 (2014)
Archetti, C., Savelsbergh, M.W.P., Speranza, M.G.: Worst-case analysis for split delivery vehicle routing problems. Transp. Sci. 40(2), 226–234 (2006)
Chen, S., Golden, B., Wasil, E.: The split delivery vehicle routing problem: Applications, algorithms, test problems, and computational results. Networks 49(4), 318–329 (2007)
Gulczynski, D., Golden, B., Wasil, E.: The split delivery vehicle routing problem with minimum delivery amounts. Transp. Res. Part E Logist. Transp. Rev. 46(5), 612–626 (2010)
Xiong, Y., Gulczynski, D., Kleitman, D., Golden, B., Wasil, E.: A worst-case analysis for the split delivery vehicle routing problem with minimum delivery amounts. Optim. Lett. 7(7), 1597–1609 (2013)