TY  - JOUR
A1  - Stenger, Andreas
A1  - Schneider, Michael
A1  - Goeke, Dominik
T1  - The prize-collecting vehicle routing problem with single and multiple depots and non-linear cost
T2  - EURO Journal on Transportation and Logistics
N2  - In this paper, we propose a new routing problem to model a highly relevant planning task in small package shipping. We consider the Prize-Collecting Vehicle Routing Problem with Non-Linear cost in its single and multi-depot version, which integrates the option of outsourcing customers to subcontractors instead of serving them with the private fleet. Thereby, a lower bound on the total customer demand to be served by the private fleet guarantees a high utilization of the fleet capacity. To represent the practical situation, where a discount is given by a subcontractor if larger amounts of packages are outsourced, subcontracting costs follow a non-linear function. The considered problem is NP-hard and we propose an Adaptive Variable Neighborhood Search algorithm to solve instances of realistic size. We propose new benchmark sets for the single and the multi-depot problem, which are adapted from test instances of the capacitated VRP and the closely related Multi-Depot VRP with Private fleet and Common carrier. In numerical studies, we investigate the performance of our algorithm on the newly generated test instances and on standard benchmark problems of related problems. Moreover, we study the effect of different cost functions and different values of the minimal demand to be served by the private fleet on the routing solutions obtained.
KW  - Vehicle routing
KW  - Prize-collecting
KW  - Heuristic
KW  - Non-linear cost
Y1  - 2020
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/76901
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30:3-769013
SN  - 2192-4376
VL  - 2
IS  - 1-2
SP  - 57
EP  - 87
PB  - Elsevier
CY  - Amsterdam
ER  -