A heuristic framework on a common generalization of the Vehicle Routing Problem and the Linear Ordering Problem

作者：Blazsik Zoltan^*; Fajfrik Zoltan Imre

来源：Central European Journal of Operations Research, 2017, 25(1): 55-70.

DOI：10.1007/s10100-015-0419-2

• VRPIT, HPPIT, LOP, TSP, VRP problems
• Combinatorial optimization
• Local search, Stochastic hill climbing and Simulated annealing algorithms

A framework for bounding and approximating the solution of a newly formulated problem, the Vehicle Routing Problem with Internal Transports (VRPIT) Blazsik 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 Stutzle (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.

• 出版日期2017-3