The multi-depot general share-a-ride problem. (1st March 2023)

• Record Type: Journal Article
• Authors: Yu, Vincent F.; Marye Zegeye, Mareg; Geremew Gebeyehu, Sisay; Indrakarna, Putu A.Y.; Jodiawan, Panca
• Is Part Of: Expert systems with applications. Volume 213:Part B(2023)
• Publication Date: 2023-03-01
• Subjects: Multi-depot -- General share-a-ride problem -- Simulated Annealing; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2022.119044
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: The Multi-Depot General Share-a-Ride Problem (MD-GSARP) is introduced. A mathematical model for MD-GSARP is developed. A simulated annealing algorithm is developed for solving MD-GSARP. The proposed SA is effective and efficient to solve MD-GSARP. Abstract: This research introduces the multi-depot general share-a-ride problem (MD-GSARP), which is an extension of the general share-a-ride problem (G-SARP). The goal of MD-GSARP is to maximize the profit from serving parcel and passenger requests with taxis that depart from several depots and return to their respective depots. We developed a mixed integer linear program for MD-GSARP and proposed a Simulated Annealing (SA) algorithm to solve the problem. The proposed algorithm consists of a deterministic insertion heuristic, a time slack strategy, two sets of neighborhood moves that depend on the time slack strategy, and a penalty mechanism for infeasible solutions. Computational results show that both the commercial solver CPLEX and our proposed SA achieve optimal solutions to small benchmark instances. Moreover, comparative results show that the proposed SA algorithm yields better solutions than the basic SA algorithm. Our analysis also reveals that MD-GSARP solutions are better than G-SARP solutions.