Dial-a-ride problem: mixed integer programming revisited and constraint programming proposed. Issue 2 (1st February 2023)

• Record Type: Journal Article
• Authors: Ham, Andy
• Is Part Of: Engineering optimization. Volume 55:Issue 2(2023)
• Page Start: 257
• Page End: 270
• Publication Date: 2023-02-01
• Subjects: Ridesharing -- DARPTW -- warm-start -- real-time rescheduling; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2021.1996570
• Languages: English
• ISSNs: 0305-215X

Abstract

Abstract : The dial-a-ride problem with time windows is studied in this article. First, a new efficient mixed integer programming formulation is proposed by merging some of drop-off nodes into paired pick-up nodes when a size of the order forbids ridesharing, so a vehicle must visit the paired drop-off nodes directly after the pick-up, thus reducing the number of decision variables by 40% on benchmark instances. Secondly, three different constraint programming formulations are proposed for the first time, generating efficient schedules within a few seconds. Thirdly, a real-time rescheduling perspective is further studied, since the ridesharing becomes dynamic when a schedule must be provided instantly. In particular, the warm-start search method, in which a precalculated schedule is continuously revised as new orders come in, is proposed.