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

Zoltán Blázsik () and Zoltán Imre Fajfrik ()
Additional contact information
Zoltán Blázsik: University of Szeged
Zoltán Imre Fajfrik: University of Szeged

Central European Journal of Operations Research, 2017, vol. 25, issue 1, No 3, 55-70

Abstract: Abstract 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.

Keywords: VRPIT; HPPIT; LOP; TSP; VRP problems; Combinatorial optimization; Local search; Stochastic hill climbing and Simulated annealing algorithms; 05C85; 68W25; 90C35; 90C27; 90C59; 90B18; 90B06 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10100-015-0419-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:cejnor:v:25:y:2017:i:1:d:10.1007_s10100-015-0419-2

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10100

DOI: 10.1007/s10100-015-0419-2

Access Statistics for this article

Central European Journal of Operations Research is currently edited by Ulrike Leopold-Wildburger

More articles in Central European Journal of Operations Research from Springer, Slovak Society for Operations Research, Hungarian Operational Research Society, Czech Society for Operations Research, Österr. Gesellschaft für Operations Research (ÖGOR), Slovenian Society Informatika - Section for Operational Research, Croatian Operational Research Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().