Decomposition algorithm for the multi-trip single vehicle routing problem with AND-type precedence constraints

Mina Roohnavazfar () and Seyed Hamid Reza Pasandideh ()
Additional contact information
Mina Roohnavazfar: Kharazmi University
Seyed Hamid Reza Pasandideh: Kharazmi University

Operational Research, 2022, vol. 22, issue 4, No 34, 4253-4285

Abstract: Abstract This paper addresses a new variant of the multi-trip single vehicle routing problem where the nodes are related to each other through AND-type precedence constraints. The problem aims at determining a sequence of trips to visit all the nodes respecting every precedence constraint within and among the routes so to minimize the total traveling cost. Our motivation comes from routing problems where a node may have a set of predecessors (not just single one proposed in the dial-a-ride or pickup and delivery problems) resulting in a set of pairwise relations that specify which customers need to be visited before which other ones. We develop three Mixed Integer Programming models to formulate the problem. The models are experimentally compared to determine the best one. Moreover, a solution approach based on the Logic-Based Benders Decomposition algorithm is developed which allows to decompose the original problem into an assignment master problem and independent sequencing subproblems. A new valid optimality cut is devised to achieve faster convergence. The cut performance is experimentally investigated by comparing with a recently proposed one in the literature. We further relax the algorithm to find the sub-optimal solution and demonstrate its efficiency. Extensive computational experiments are conducted to assess the proposed algorithms in terms of solution quality and CPU time.

Keywords: Capacitated single vehicle routing problem; AND-type precedence constraints; Multiple trips; Logic based benders decomposition algorithm (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-021-00663-0 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:operea:v:22:y:2022:i:4:d:10.1007_s12351-021-00663-0

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-021-00663-0

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().