期刊
DISCRETE APPLIED MATHEMATICS
卷 288, 期 -, 页码 152-170出版社
ELSEVIER
DOI: 10.1016/j.dam.2020.08.014
关键词
Vehicle routing; Multiple vehicle traveling purchaser problem; Unitary demand; Incompatible products; Column generation; Dynamic-programming labeling algorithm
资金
- Deutsche Forschungsgemeinschaft (DFG) [IR 122/5-2, IR 122/9-2]
- Regione Lombardia [E97F17000000009]
This study discusses variants of the Multiple Vehicle Traveling Purchaser Problem (MVTPP), introduces a branch-price-and-cut algorithm, proposes a new branching rule and valid inequalities, and demonstrates how to handle product incompatibilities. Experimental results show that the new approach is highly competitive.
The multiple vehicle traveling purchaser problem (MVTPP) consists of simultaneously selecting suppliers and routing a fleet of homogeneous vehicles to purchase different products at the selected suppliers so that all product demands are fulfilled and traveling and purchasing costs are minimized. We consider variants of the MVTPP in which the capacity of the vehicles can become binding and the demand for each product is one unit. Corresponding solution algorithms from the literature are either branch-and-cut or branch-and-price algorithms, where in the latter case the route-generation subproblem is solved on an expanded graph by applying standard dynamic-programming techniques. Our branch-price-and-cut algorithm employs a novel labeling algorithm that works directly on the original network and postpones the purchasing decisions until the route has been completely defined. Moreover, we define a new branching rule generally applicable in case of unitary product demands, introduce a new family of valid inequalities to apply when suppliers can be visited at most once, and show how product incompatibilities can be handled without considering additional resources in the pricing problem. In comprehensive computational experiments with standard benchmark sets we prove that the new branch-price-and-cut approach is highly competitive. (C) 2020 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据