Branch‐and‐price‐and‐cut for the manpower routing problem with synchronization constraints. (31st March 2016)

• Record Type: Journal Article
• Authors: Luo, Zhixing; Qin, Hu; Zhu, Wenbin; Lim, Andrew
• Is Part Of: Naval research logistics. Volume 63:Number 2(2016:Mar.)
• Page Start: 138
• Page End: 171
• Publication Date: 2016-03-31
• Subjects: routing -- manpower scheduling -- synchronization -- branch‐and‐price‐and‐cut; Logistics, Naval -- Periodicals; Supplies and stores -- Periodicals; 359.07
• DOI: 10.1002/nav.21683
• Languages: English
• ISSNs: 0894-069X

Abstract

Abstract: In this article, we propose a branch‐and‐price‐and‐cut (BPC) algorithm to exactly solve the manpower routing problem with synchronization constraints (MRPSC). Compared with the classical vehicle routing problems (VRPs), the defining characteristic of the MRPSC is that multiple workers are required to work together and start at the same time to carry out a job, that is, the routes of the scheduling subjects are dependent. The incorporation of the synchronization constraints increases the difficulty of the MRPSC significantly and makes the existing VRP exact algorithm inapplicable. Although there are many types of valid inequalities for the VRP or its variants, so far we can only adapt the infeasible path elimination inequality and the weak clique inequality to handle the synchronization constraints in our BPC algorithm. The experimental results at the root node of the branch‐and‐bound tree show that the employed inequalities can effectively improve the lower bound of the problem. Compared with ILOG CPLEX, our BPC algorithm managed to find optimal solutions for more test instances within 1 hour. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 138–171, 2016