The Capacitated Team Orienteering Problem With Transfers and Synchronization

Date

2026-8-6

Author

Külekçi, Beste

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

40
views

0
downloads

Cite This

This thesis introduces the Capacitated Team Orienteering Problem with Transfers and Synchronization (CTOPT-S), a profit-maximizing selective routing problem in which vehicles may exchange load directly at customer nodes, and in which these exchanges are required to be temporally synchronized. The problem combines two cooperative mechanisms: split delivery and inter-vehicle transfers. A mixed-integer linear programming formulation is developed, together with a branch-and-cut algorithm that separates connectivity inequalities dynamically. Because exact methods do not scale to the largest instances, an Adaptive Large Neighborhood Search heuristic with transfer-specific operators is also proposed to obtain good-quality solutions more quickly. Computational experiments on the benchmark instances show that the CTOPT-S provides an advantage over using only split-deliveries, demonstrated on a few instances. The branch-and-cut algorithm we proposed is computationally more efficient than the MILP model. The heuristic we designed delivers better solutions than the exact method on the large instances that neither exact method solves to optimality within three hours. A regime analysis further shows that cooperation between vehicles is more valuable when the capacity constraints of the vehicles are binding, while route duration constraints are less significant for the improvement.

Subject Keywords

Capacitated Team Orienteering Problem, Inter-Vehicle Transfers, Split-Deliveries, Branch-and-Cut, ALNS

URI

https://hdl.handle.net/11511/120092

Collections

Graduate School of Natural and Applied Sciences, Thesis