Inefficiencies in transportation have resulted in economic and environmental problems.
High levels of traffic jam leads to the increase of air pollution and waste of resource. To
handle this issue, the Share-a-Ride Problem (SARP) was developed. In SARP, passenger and parcel requests could be served at the same time by a taxi. Moreover, to handle those problems more efficiently, some extensions of SARP have been proposed such as General Share-a-Ride Problem (G-SARP). In this study, one more extended version of SARP is proposed, namely the Electric Share-a-Ride Problem (E-SARP) whose goals are reducing air pollution and traffic congestion. Instead of using taxis for making service, E-SARP uses electric vehicles (EVs) to serve requests. With using electric vehicles, air pollution could be reduced leading to going down of greenhouse gas (GHG) emissions and fuel resources. The objective of E-SARP is similar to SARP which is maximizing total profit obtained from serving passenger and parcel requests. The mathematical for E-SARP is developed and CPLEX is used to find out exact solution from small instances. Simulated Annealing (SA) algorithm is proposed for solving the problem. For small instances, the results of SARP and E-SARP are quite similar and for large instances, the gaps are very small and the average percentage gap is positive; 1.93%. From this result, it can be proved that E-SARP not only can obtain good solutions compared to SARP, but also can solve the environment and energy problem by using electric vehicles.

Agatz, N., Erera, A., Savelsbergh, M., & Wang, X. (2012). Optimization for dynamic ridesharing: A review. European Journal of Operational Research, 223(2), 295–303.
https://doi.org/10.1016/j.ejor.2012.05.028
Bongiovanni, C., Kaspi, M., & Geroliminis, N. (2019). The electric autonomous dial-a-ride problem. Transportation Research Part B, 122, 436–456.
https://doi.org/10.1016/j.trb.2019.03.004
Chen, W., Mes, M., Schutten, M., & Quint, J. (2019). A ride-sharing problem with meeting points and return restrictions. Transportation Science, 53(2), 401–426.
https://doi.org/10.1287/trsc.2018.0832
Cherkesly, M., Desaulniers, G., & Laporte, G. (2015). A population-based metaheuristic for the pickup and delivery problem with time windows and LIFO loading. Computers and Operations Research, 62, 23–35. https://doi.org/10.1016/j.cor.2015.04.002
Clarke, G., & Wright, J. W. (1964). Scheduling of Vehicles from a Central Depot to a
Number of Delivery Points. Operations Research, 12(4), 568–581.
https://doi.org/10.1287/opre.12.4.568
Cordeau, J. F., & Laporte, G. (2003a). A tabu search heuristic for the static multi-vehicle
dial-a-ride problem. Transportation Research Part B: Methodological, 37(6), 579–594.
https://doi.org/10.1016/S0191-2615(02)00045-0
Cordeau, J. F., & Laporte, G. (2003b). The Dial-a-Ride Problem (DARP): Variants, modeling issues and algorithms. 4or, 1(2), 89–101. https://doi.org/10.1007/s10288-002-0009-8
Cordeau, J. F., & Laporte, G. (2007). The dial-a-ride problem: Models and algorithms.
Annals of Operations Research, 153(1), 29–46. https://doi.org/10.1007/s10479-007-
0170-8
dantzig1959.pdf. (n.d.).
Deng, A. M., Mao, C., & Zhou, Y. T. (2009). Optimizing research of an improved simulated annealing algorithm to soft time windows vehicle routing problem with pick-up and delivery. Xitong Gongcheng Lilun Yu Shijian/System Engineering Theory and Practice, 29(5), 186–192. https://doi.org/10.1016/s1874-8651(10)60049-x
Desaulniers, G., Errico, F., Irnich, S., Schneider, M., Desaulniers, G., Irnich, S., & Schneider,
M. (2016). Exact Algorithms for Electric Vehicle-Routing.pdf, (November).
Furuhata, M., Dessouky, M., Ordóñez, F., Brunet, M. E., Wang, X., & Koenig, S. (2013).
Ridesharing: The state-of-the-art and future directions. Transportation Research Part B:
Methodological, 57, 28–46. https://doi.org/10.1016/j.trb.2013.08.012
Gas, R., & To, R. U. P. (2003). Unfccc p. Environment, (October).
Goeke, D., & Schneider, M. (2015). Routing a mixed fleet of electric and conventional
vehicles. European Journal of Operational Research, 245(1), 81–99.
https://doi.org/10.1016/j.ejor.2015.01.049
Greenhouse gas emissions from transport in Europe — European Environment Agency.
(n.d.). Retrieved January 21, 2021, from https://www.eea.europa.eu/data-andmaps/indicators/transport-emissions-of-greenhouse-gases/transport-emissions-ofgreenhouse-gases-11
H, N. (1986). DPT ,( DDTj ; i. Time, 2(3), 243–257.
Keskin, M., & Çatay, B. (2016). Partial recharge strategies for the electric vehicle routing
problem with time windows. Transportation Research Part C: Emerging Technologies,
65, 111–127. https://doi.org/10.1016/j.trc.2016.01.013
Kleiner, A., Nebel, B., & Ziparo, V. A. (2011). A mechanism for dynamic ride sharing based on parallel auctions. IJCAI International Joint Conference on Artificial Intelligence, 266–272. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-055
Laporte, G. (1992). The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(2), 231–247.
https://doi.org/10.1016/0377-2217(92)90138-Y
Li, B., Krushinsky, D., Reijers, H. A., & Van Woensel, T. (2014). The Share-A-Ride
Problem: People and parcels sharing taxis. European Journal of Operational Research,
238(1), 31–40. https://doi.org/10.1016/j.ejor.2014.03.003
Li, B., Krushinsky, D., Van Woensel, T., & Reijers, H. A. (2016a). An adaptive large
neighborhood search heuristic for the share-a-ride problem. Computers and Operations Research, 66, 170–180. https://doi.org/10.1016/j.cor.2015.08.008
Li, B., Krushinsky, D., Van Woensel, T., & Reijers, H. A. (2016b). The Share-a-Ride
problem with stochastic travel times and stochastic delivery locations. Transportation
Research Part C: Emerging Technologies, 67, 95–108.
https://doi.org/10.1016/j.trc.2016.01.014
Liu, R., Xie, X., Augusto, V., & Rodriguez, C. (2013). Heuristic algorithms for a vehicle
routing problem with simultaneous delivery and pickup and time windows in home
health care. European Journal of Operational Research, 230(3), 475–486.
https://doi.org/10.1016/j.ejor.2013.04.044
Masmoudi, M. A., Hosny, M., Demir, E., Genikomsakis, K. N., & Cheikhrouhou, N. (2018).
The dial-a-ride problem with electric vehicles and battery swapping stations.
Transportation Research Part E: Logistics and Transportation Review, 118(August),
392–420. https://doi.org/10.1016/j.tre.2018.08.005
Montoya, A., Gu, C., Mendoza, J. E., Villegas, J., Mendoza, J. E., & Villegas, J. (2015). The
electric vehicle routing problem with partial charging and nonlinear charging function
To cite this version : The electric vehicle routing problem with partial charging and
nonlinear charging function par « Alejandro Montoya , Christelle Guéret , Jorg.
Montoya, A., Guéret, C., Mendoza, J. E., & Villegas, J. G. (2017). The electric vehicle
routing problem with nonlinear charging function. Transportation Research Part B:
Methodological, 103, 87–110. https://doi.org/10.1016/j.trb.2017.02.004
Nagy, G., & Salhi, S. (2005). Heuristic algorithms for single and multiple depot vehicle
routing problems with pickups and deliveries. European Journal of Operational
Research, 162(1), 126–141. https://doi.org/10.1016/j.ejor.2002.11.003
Parragh, S. N., Doerner, K. F., & Hartl, R. F. (2010). Variable neighborhood search for the
dial-a-ride problem. Computers and Operations Research, 37(6), 1129–1138.
https://doi.org/10.1016/j.cor.2009.10.003
Psaraftis, H. N. (1980). Dynamic Programming Solution To the Single Vehicle Many-ToMany Immediate Request Dial-a-Ride Problem. Transportation Science, 14(2), 130–
154. https://doi.org/10.1287/trsc.14.2.130
Schiffer, M., & Walthera, G. (2018). An adaptive large neighborhood search for the locationrouting problem with intra-route facilities. Transportation Science, 52(2), 331–352. https://doi.org/10.1287/trsc.2017.0746
Schneider, M., Stenger, A., & Goeke, D. (2014). The electric vehicle-routing problem with time windows and recharging stations. Transportation Science, 48(4), 500–520.
https://doi.org/10.1287/trsc.2013.0490
United States of America. (2016). United States Intended Nationally Determined
Contribution. Un, 2025(NOVEMBER), 1–7. Retrieved from
http://www4.unfccc.int/ndcregistry/PublishedDocuments/United States of America
First/U.S.A. First NDC Submission.pdf
US EPA, O. (n.d.). Fast Facts on Transportation Greenhouse Gas Emissions. Retrieved from https://www.epa.gov/greenvehicles/fast-facts-transportation-greenhouse-gas-emissions
Yu, V. F., Purwanti, S. S., Redi, A. A. N. P., Lu, C. C., Suprayogi, S., & Jewpanya, P.
(2018). Simulated annealing heuristic for the general share-a-ride problem. Engineering Optimization, 50(7), 1178–1197. https://doi.org/10.1080/0305215X.2018.1437153