Simulated annealing heuristic for the general share-a-ride problem

ABSTRACT

This research introduces an extension of the share-a-ride problem (SARP), called the general share-a-ride problem (G-SARP). Similarly to SARP, a taxi in G-SARP can service passenger and package requests at the same time. However, G-SARP allows the taxi to transport more than one passenger at the same time, which is more beneficial in practical situations. In addition, G-SARP has no restrictions on the maximum riding time of a passenger, and the number of parcel requests that can be inserted between the pick-up and drop-off points of a passenger is limited only by vehicle capacity. A simulated annealing (SA) algorithm is proposed to solve G-SARP. The proposed SA algorithm is compared with basic SA and tabu search (TS) algorithms. The results show that the proposed SA algorithm outperforms basic SA and TS algorithms. Moreover, further analysis shows that G-SARP solutions are better than those of SARP in most cases.

KEYWORDS:

• General share-a-ride problem
• ride sharing
• share-a-ride problem
• simulated annealing

Acknowledgement

The authors gratefully acknowledge support from the Ministry of Science and Technology of the Republic of China (Taiwan).

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Vincent F. Yu http://orcid.org/0000-0001-8975-0606

A. A. N. Perwira Redi http://orcid.org/0000-0003-3520-5260

Chung-Cheng Lu http://orcid.org/0000-0001-8317-4193

Additional information

Funding

This research was partially supported by the Ministry of Science and Technology of the Republic of China (Taiwan) [grant numbers MOST 106-2410-H-011-002-MY3 and MOST 105-2811-E-011-017].