A worst-case analysis for the split delivery capacitated team orienteering problem with minimum delivery amounts

作者：Wang Xingyin^*; Golden Bruce; Gulczynski Damon

来源：Optimization Letters, 2014, 8(8): 2349-2356.

DOI：10.1007/s11590-014-0752-8

• Team orienteering problem
• Worst-case analysis
• Split delivery
• Minimum delivery amount

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.

• 出版日期2014-12