Simulated Annealing with Mutation Strategy for the Share-a-Ride Problem with Flexible Compartments

Vincent F. Yu, Putu A. Y. Indrakarna, Anak Agung Ngurah Perwira Redi and Shih-Wei Lin
Additional contact information
Vincent F. Yu: Department of Industrial Management, National Taiwan University of Science and Technology, Taipei 106, Taiwan
Putu A. Y. Indrakarna: Department of Industrial Management, National Taiwan University of Science and Technology, Taipei 106, Taiwan
Anak Agung Ngurah Perwira Redi: BINUS Graduate Program—Master of Industrial Engineering, Industrial Engineering Department, Bina Nusantara University, Jakarta 11480, Indonesia
Shih-Wei Lin: Department of Information Management, Chang Gung University, Taoyuan 333, Taiwan

Mathematics, 2021, vol. 9, issue 18, 1-18

Abstract: The Share-a-Ride Problem with Flexible Compartments (SARPFC) is an extension of the Share-a-Ride Problem (SARP) where both passenger and freight transport are serviced by a single taxi network. The aim of SARPFC is to increase profit by introducing flexible compartments into the SARP model. SARPFC allows taxis to adjust their compartment size within the lower and upper bounds while maintaining the same total capacity permitting them to service more parcels while simultaneously serving at most one passenger. The main contribution of this study is that we formulated a new mathematical model for the problem and proposed a new variant of the Simulated Annealing (SA) algorithm called Simulated Annealing with Mutation Strategy (SAMS) to solve SARPFC. The mutation strategy is an intensification approach to improve the solution based on slack time, which is activated in the later stage of the algorithm. The proposed SAMS was tested on SARP benchmark instances, and the result shows that it outperforms existing algorithms. Several computational studies have also been conducted on the SARPFC instances. The analysis of the effects of compartment size and the portion of package requests to the total profit showed that, on average, utilizing flexible compartments as in SARPFC brings in more profit than using a fixed-size compartment as in SARP.

Keywords: share-a-ride; flexible compartment; simulated annealing; mutation strategy (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/18/2320/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/18/2320/ (text/html)

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:gam:jmathe:v:9:y:2021:i:18:p:2320-:d:638976

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().