Problem of Patient Transport Route Planning for Battery Electric Vehicles Considering a Flexible Charging Strategy

Abstract

In view of the current problem of non-emergency patient transport route planning, the research is mainly carried out on fuel vehicles, and in the related research on the vehicle routing problem of electric vehicles, the relevant research results considering flexible charging strategies of different charging technologies are relatively weak. Therefore, this paper studies the non-emergency patient transport route planning problem based on pure electric vehicles, introduces a flexible charging strategy, constructs a mathematical model with the goal of maximizing the average patient satisfaction and minimizing the total cost of patient transport, and designs a hybrid heuristic algorithm to solve the problem. Then, different algorithms are used to solve the mathematical model considering patient satisfaction and the mathematical model not considering patient satisfaction. The feasibility and applicability of the mathematical model and the hybrid algorithm are verified by comparing and analyzing the solution results of different algorithms. Finally, based on the hybrid heuristic algorithm, the mathematical model of non-emergency patient transport route planning considering different charging strategies is solved. The applicability and reliability of the hybrid algorithm are further verified by comparing the solution results of different charging strategies, which shows that the flexible charging strategy can not only achieve a better balance between patient satisfaction and the total cost of patient transport, but also effectively improve the utilization efficiency of the remaining power of the vehicle.

Keywords

patient transport electric vehicle routing problem battery electric vehicle patient satisfaction flexible charging strategy hybrid algorithm

Get full access to this article

View all access options for this article.

References

Psaraftis

H. N.

A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem. Transportation Science, Vol. 14, No. 2, 1980, pp. 130–154. https://doi.org/10.1287/trsc.14.2.130.

Cordeau

J. F.

Laporte

The Dial-a-Ride Problem: Models and Algorithms. Annals of Operations Research, Vol. 153, 2007, pp. 29–46. https://doi.org/10.1007/s10479-007-0170-8.

S. C.

Szeto

W. Y.

Kuo

Leung

Petering

M. E.

Tou

T.W.

A Survey of Dial-a-Ride Problems: Literature Review and Recent Developments. Transportation Research Part B: Methodological, Vol. 111, 2018, pp. 395–421. https://doi.org/10.1016/j.trb.2018.02.001.

Bowers

Lyons

Mould

Developing a Resource Allocation Model for the Scottish Patient Transport Service. Operations Research for Health Care, Vol. 1, No. 4, 2012, pp. 84–94. https://doi.org/10.1016/j.orhc.2012.10.002.

Madsen

O. B. G.

Ravn

H. F.

Rygaard

J. M.

A Heuristic Algorithm for a Dial-a-Ride Problem with Time Windows, Multiple Capacities, and Multiple Objectives. Annals of Operations Research, Vol. 60, 1995, pp. 193–208. https://doi.org/10.1007/BF02031946.

Rekiek

Delchambre

Saleh

H. A.

Handicapped Person Transportation: An Application of the Grouping Genetic Algorithm. Engineering Applications of Artificial Intelligence, Vol. 19, No. 5, 2006, pp. 511–520. https://doi.org/10.1016/j.engappai.2005.12.013.

Melachrinoudis

Ilhan

A. B.

Min

A Dial-a-Ride Problem for Client Transportation in a Health Care Organization. Computers & Operations Research, Vol. 34, No. 3, 2007, pp. 742–759. https://doi.org/10.1016/j.cor.2005.03.024.

Parragh

S. N.

Ambulance Routing Problems with Rich Constraints and Multiple Objectives. Dissertation. Universität Wien, 2009.

Carnes

Henderson

S. G.

Shmoys

D. B.

Ahghari

MacDonald

Mathematical Programming Guides Air-Ambulance Routing at Ornge. Interfaces, Vol. 43, 2013, pp. 232–239. https://doi.org/10.1287/inte.2013.0683.

10.

Oliveira

J. A.

Ferreira

Dias

Figueiredo

Pereira

Non-emergency Patients Transport - A Mixed Integer Linear Programming. International Conference on Operations Research and Enterprise Systems, Vol. 1, 2015, pp. 262–269. https://doi.org/10.5220/0005214902620269.

11.

Molenbruch

Braekers

Canis

Berghe

G. V.

Multi-Directional Local Search for a Bi-objective Dial-a-Ride Problem in Patient Transportation. Computers & Operations Research, Vol. 77, 2017, pp. 58–71. https://doi.org/10.1016/j.cor.2016.07.020.

12.

Detti

Papalini

Lara

G. Z. M. D.

A Multi-Depot Dial-a-Ride Problem with Heterogeneous Vehicles and Compatibility Constraints in Healthcare. Omega, Vol. 70, 2017, pp. 1–14. https://doi.org/10.1016/j.omega.2016.08.008.

13.

Oliveira

J. A.

Ferreira

Figueiredo

Dias

Pereira

G. A. B.

Genetic Algorithms for the Non-emergency Patient Transport Service. Proceedings of the 18th Online World Conference on Soft Computing in Industrial Applications (WSC18), Vol. 864, 2019, pp. 95–106. https://doi.org/10.1007/978-3-030-00612-9_9.

14.

Nasir

J. A.

Kuo

Y. H.

Cheng

Clustering-Based Iterative Heuristic Framework for a Non-emergency Patient Transportation Problem. Journal of Transport & Health, Vol. 26, 2022, p. 101411. https://doi.org/10.1016/j.jth.2022.101411.

15.

Attari

M. Y. N.

Ahmadi

Ala

Moghadamnia

RSDM-AHSnet: Designing a Robust Stochastic Dynamic Model to Allocating Health Service Network Under Disturbance Situations with Limited Capacity Using Algorithms NSGA-II and PSO. Computers in Biology and Medicine, Vol. 147, 2022, p. 105649. https://doi.org/10.1016/j.compbiomed.2022.105649.

16.

Zhang

Z Z.

Liu

M. Y.

Lim

A Memetic Algorithm for the Patient Transportation Problem. Omega, Vol. 54, 2015, pp. 60–71. https://doi.org/10.1016/j.omega.2015.01.011.

17.

Lim

Zhang

Z. Z.

Qin

Pickup and Delivery Service with Manpower Planning in Hong Kong Public Hospitals. Transportation Science, Vol. 51, No. 2, 2017, pp. 688–705. https://doi.org/10.1287/trsc.2015.0611.

18.

Luo

M. L.

Yuan

P. C.

Modeling and Comparative Analysis of Patient Transportation by Fuel and Electric Vehicles. Computer Systems and Applications, Vol. 31, No. 12, 2022, pp. 368–374. https://doi.org/10.15888/j.cnki.csa.008784.

19.

Zhang

Gajpal

Appadoo

S. S.

Abdulkader

M. M. S.

Electric Vehicle Routing Problem with Recharging Stations for Minimizing Energy Consumption. International Journal of Production Economics, Vol. 203, 2018, pp. 404–413. https://doi.org/10.1016/j.ijpe.2018.07.016.

20.

Barco

Guerra

Muñoz

Quijano

Optimal Routing and Scheduling of Charge for Electric Vehicles: A Case Study. Mathematical Problems in Engineering, Vol. 2017, 2017, pp. 8509783.1–8509783.16. https://doi.org/10.1155/2017/8509783.

21.

Felipe

Á.

Ortuño

M. T.

Righini

Tirado

A Heuristic Approach for the Green Vehicle Routing Problem with Multiple Technologies and Partial Recharges. Transportation Research Part E: Logistics and Transportation Review, Vol. 71, 2014, pp. 111–128. https://doi.org/10.1016/j.tre.2014.09.003.

22.

Schiffer

Walther

The Electric Location Routing Problem with Time Windows and Partial Recharging. European Journal of Operational Research, Vol. 260, No. 3, 2017, pp. 995–1013. https://doi.org/10.1016/j.ejor.2017.01.011.

23.

Verma

Electric Vehicle Routing Problem with Time Windows, Recharging Stations and Battery Swapping Stations. EURO Journal on Transportation and Logistics, Vol. 7, No. 4, 2018, pp. 415–451. https://doi.org/10.1007/s13676-018-0136-9.

24.

Hiermann

Puchinger

Ropke

Hartl

R. F.

The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations. European Journal of Operational Research, Vol. 252, 2016, pp. 995–1018. https://doi.org/10.1016/j.ejor.2016.01.038.

25.

Macrina

Laporte

Guerriero

Pugliese

L. D. P.

An Energy-Efficient Green-Vehicle Routing Problem with Mixed Vehicle Fleet, Partial Battery Recharging and Time Windows. European Journal of Operational Research, Vol. 276, No. 3, 2019, pp. 971–982. https://doi.org/10.1016/j.ejor.2019.01.067.

26.

Qin

X. X.

Ren

Luo

Z. X.

A Review on the Electric Vehicle Routing Problems: Variants and Algorithms. Frontiers of Engineering Management, Vol. 8, No. 3, 2021, pp. 370–389. https://doi.org/10.1007/s42524-021-0157-1.

27.

C. J.

W. J.

Chen

H. Q.

Electric Vehicle Routing Models and Solution Algorithms in Logistics Distribution: A Systematic Review. Environmental Science and Pollution Research, Vol. 29, 2022, pp. 57067–57090. https://doi.org/10.1007/s11356-022-21559-2.

28.

Guo

Yang

Research on Electric Vehicle Route Optimization Considering Charging Strategy and Battery Loss. Chinese Journal of Management Science, Vol. 26, No. 9, 2018, pp. 106–118. https://doi.org/10.16381/j.cnki.issn1003-207x.2018.09.011.

29.

Chen

Zhang

B. W.

Pourbabak

Kavousi-Fard

W. C.

Optimal Routing and Charging of an Electric Vehicle Fleet for High-Efficiency Dynamic Transit Systems. IEEE Transactions on Smart Grid, Vol. 9, No. 4, 2018, pp. 3563–3572. https://doi.org/10.1109/TSG.2016.2635025.

30.

Jie

W. C.

Yang

Zhang

Huang

Y. X.

The Two-Echelon Capacitated Electric Vehicle Routing Problem with Battery Swapping Stations: Formulation and Efficient Methodology. European Journal of Operational Research, Vol. 272, No. 3, 2019, pp. 879–904. https://doi.org/10.1016/j.ejor.2018.07.002.

31.

Wang

Q. Y.

Study on Site Selection Route Problem of Electric Vehicle Swap Station with Soft Time Window. Industrial Engineering and Management, Vol. 24, No. 3, 2019, pp. 99–106. https://doi.org/10.19495/j.cnki.1007-5429.2019.03.013.

32.

Zhang

B. D.

Yan

Zhang

H. R.

Electric Vehicle Charging and Swapping Route Planning Method Based on Real-Time Traffic Information. Journal of Jilin University (Engineering and Technology Edition), Vol. 52, No. 10, 2022, pp. 2333–2342. https://doi.org/10.13229/j.cnki.jdxbgxb20211094.

33.

Zhang

M. Y.

Yang

Huang

S. Y.

Y. Q.

Multi-Vehicle Electric Bus Scheduling Optimization Considering Orderly Charging Strategy. Journal of Jilin University (Engineering and Technology Edition), Vol. 3, 2023, pp. 1–9. https://doi.org/10.13229/j.cnki.jdxbgxb20220820.

34.

Lim

M. K.

Tan

Y. S.

Lee

S. Y.

Tseng

M. L.

Sharing Economy to Improve Routing for Urban Logistics Distribution Using Electric Vehicles. Resources, Conservation and Recycling, Vol. 153, 2020, p. 104585. https://doi.org/10.1016/j.resconrec.2019.104585.

35.

Shao

Guan

Electric Vehicle Routing Problem with Charging Demands and Energy Consumption. IET Intelligent Transport Systems, Vol. 12, No. 3, 2018, pp. 202–212. https://doi.org/10.1049/iet-its.2017.0008.

36.

Jie

W. C.

Yang

Split Delivery Routing Problem of Electric Vehicles and Its Modified Branch-and-Price Algorithm. Chinese Journal of Management, Vol. 17, No. 12, 2022, pp. 1873–1880.

37.

Shaw

Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems. Proc., International Conference on Principles and Practice of Constraint Programming, Pisa, Italy, 1998. https://doi.org/10.1007/3-540-49481-2_30.