Two heuristics for the capacitated minimum spanning tree problem with time windows

Manolis N. Kritikos and George Ioannou

Journal of the Operational Research Society, 2019, vol. 70, issue 4, 555-567

Abstract: We consider the capacitated minimum spanning tree problem with time windows (CMSTPTW) and propose an enhancement of greedy heuristic for the uncapacitated version of it, showing that our algorithm significantly outperforms Solomon’s one based on the R7 test problem. To examine the performance of our approach, we convert the vehicle routing data sets to appropriately model CMSTPTW instances and provide solutions for all of them; in addition, we compare the solutions we reach for the uncapacitated version of all instances and those obtained by Solomon to demonstrate the consistent superiority of the proposed method. Finally, we develop a second solution approach, the local domain priority heuristic, which when applied to the same data sets results in better solutions for the majority of the CMSTPTW instances, without excessive computational effort.

Date: 2019
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2018.1447255 (text/html)
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:taf:tjorxx:v:70:y:2019:i:4:p:555-567

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2018.1447255

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().