A heuristic framework on a common generalization of the Vehicle Routing Problem and the Linear Ordering Problem
详细信息 查看全文
- 作者：Zoltán Blázsik ; Zoltán Imre Fajfrik
- 关键词：VRPIT ; HPPIT ; LOP ; TSP ; VRP problems ; Combinatorial optimization ; Local search ; Stochastic hill climbing and Simulated annealing algorithms
- 刊名：Central European Journal of Operations Research
- 出版年：2017
- 出版时间：March 2017
- 年：2017
- 卷：25
- 期：1
- 页码：55-70
- 全文大小：
- 刊物主题：Operation Research/Decision Theory;
- 出版者：Springer Berlin Heidelberg
- ISSN：1613-9178
- 卷排序：25
文摘
A framework for bounding and approximating the solution of a newly formulated problem, the Vehicle Routing Problem with Internal Transports (VRPIT) Blázsik et al. (Pure Math Appl 17: 229–239, 2006), is presented. VRPIT is a common generalization of two well-known NP-hard problems, the Vehicle Routing Problem (VRP) Laporte (Eur J Op Res 59(3):345–358, 1992) and the Linear Ordering Problem (LOP) Schiavinotto and Stützle (J Math Model Algorithms 3(4):367–402, 2004). This generalization was motivated by the following situation: Consider VRP with the additional opportunity that each vehicle may make internal transports via short tours during its overall tour. In order to obtain the optimal income, we want to reduce the cost of small tours in relation to the profit that can be achieved by the corresponding internal transports with unit capacities. The structure of feasible solutions can be viewed as cycles of a permutation. The objective function is the difference between the profit from internal transports and the cost of the short tours. Although VRPIT is coming from the generalization of VRT and LOP, other equally hard problems can be reduced to it, as well.