Iterative Column Generation Algorithm for Generalized Multi-Vehicle Covering Tour Problem

Keisuke Murakami ()
Additional contact information
Keisuke Murakami: Kansai University 3-3-35 Yamate, Suita, Osaka 564-8680, Japan

Asia-Pacific Journal of Operational Research (APJOR), 2018, vol. 35, issue 04, 1-22

Abstract: The multi-vehicle covering tour problem (m-CTP) is defined on a graph G = (V ∪ W,E), where V is a set of vertices that can be visited and W is a set of vertices that must be covered but cannot be visited. The objective of the m-CTP is to obtain a set of total minimum cost tours on subset of V, while covering all v ∈ W by up to m vehicles. In this paper, we first generalize the original m-CTP by adding a realistic constraint, and then propose an algorithm for the generalized m-CTP using a column generation approach. Computational experiments show that our algorithm performs well and outperforms the existing algorithms.

Keywords: Covering tour problem; traveling salesman problem; set-covering problem; column generation; heuristic algorithm (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595918500215
Access to full text is restricted to subscribers

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:wsi:apjorx:v:35:y:2018:i:04:n:s0217595918500215

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595918500215

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().