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

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.