The multi-vehicle profitable pickup and delivery problem

详细信息    查看全文

• 作者：Margaretha Gansterer ; Murat Küçüktepe ; Richard F. Hartl
• 关键词：Pickup and delivery ; Profitable tour problem ; Metaheuristics
• 刊名：OR Spectrum
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：39
• 期：1
• 页码：303-319
• 全文大小：503KB
• 刊物主题：Operation Research/Decision Theory; Calculus of Variations and Optimal Control; Optimization; Business and Management, general;
• 出版者：Springer Berlin Heidelberg
• ISSN：1436-6304
• 卷排序：39

文摘

The transportation industry expanded rapidly in a highly competitive environment. Logistics companies with insufficient volume of transport capacities are forced to make a selection of customers that they can integrate efficiently into their tours. This is of particular relevance in the pickup and delivery market, where shipments from several different customers can be moved on the same vehicle. In the literature, however, the problem of customer selection has not been applied for the given class of pickup and delivery problems so far. We want to fill this gap by introducing the multi-vehicle profitable pickup and delivery problem (MVPPDP), where multiple carriers transport goods from a selection of pickup customers to the corresponding delivery customers within given travel time limits. For this problem, we propose a method based on general variable neighborhood search (GVNS). We conduct experiments with two different variants of this method, namely a sequential (GVNSseq) and a self-adaptive (GVNSsa) version. Additionally, we compare it to an algorithm based on Guided Local Search (GLS), which is known to find good solutions for related problems very fast. The performance of these methods is examined on the basis of data instances with up to 1000 customer requests. In an experimental study, we observe that both variants of GVNS with 11 neighborhoods outperform GLS with regard to solution quality for all sizes of test instances. However, for medium sized and large instances, GLS shows an advantage in average runtimes.