{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:06:45Z","timestamp":1760148405584,"version":"build-2065373602"},"reference-count":47,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2023,4,27]],"date-time":"2023-04-27T00:00:00Z","timestamp":1682553600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Natural Science Foundation of China","award":["72271222","71871203","L1924063"],"award-info":[{"award-number":["72271222","71871203","L1924063"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In the present paper, the online valet driving problem (OVDP) is studied. In this problem, customers request a valet driving service through the platform, then the valets arrive on e-bikes at the designated pickup location and drive the vehicle to the destination. The key task is to assign the valets effectively for driving orders to minimize the overall cost. To serve that purpose, we first propose a new online scheduling strategy that divides the planning horizon into several rounds with fixed length of time, and each round consists of pooling time and scheduling time. By including the features of online scheduling and the power level of e-bikes, this OVDP becomes more practical but nevertheless challenging. To solve the OVDP, we formulate it into a set partitioning model and design a branch-and-price (B&amp;P) algorithm. To improve the computation efficiency, a label setting algorithm is incorporated to address the pricing subproblem, which is accelerated via a heuristic pricing method. As an essential part of the algorithm design, an artificial column technique and a greedy-based constructive heuristic are implemented to obtain the initial solution. Based on the numerical analysis of various scaled instances, it is verified that the proposed B&amp;P algorithm is not only effective in optimum seeking, but also shows a high level of efficiency in comparison with the off-the-shelf commercial solvers. Furthermore, we also explore the impact of pooling and scheduling time on the OVDP and discover a bowl-shaped trend of the objective value with respect to the two time lengths.<\/jats:p>","DOI":"10.3390\/a16050224","type":"journal-article","created":{"date-parts":[[2023,4,27]],"date-time":"2023-04-27T04:30:47Z","timestamp":1682569847000},"page":"224","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Branch-and-Price Algorithm for the Online Scheduling of Valet Drivers"],"prefix":"10.3390","volume":"16","author":[{"given":"Lei","family":"Zhang","sequence":"first","affiliation":[{"name":"College of Mechanical Engineering, Zhejiang University of Technology, Hangzhou 310023, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6808-1490","authenticated-orcid":false,"given":"Zhi","family":"Pei","sequence":"additional","affiliation":[{"name":"College of Mechanical Engineering, Zhejiang University of Technology, Hangzhou 310023, China"}]}],"member":"1968","published-online":{"date-parts":[[2023,4,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1177\/109019819201900407","article-title":"Perspective: The Role of Designated Driver Programs in the Prevention of Alcohol-Impaired Driving: A Critical Reassessment","volume":"19","author":"DeJong","year":"1992","journal-title":"Health Educ. Q."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1136\/ip.2006.015032","article-title":"Drinking behaviors in young adults: The potential role of designated driver and safe ride home programs","volume":"13","author":"Rivara","year":"2007","journal-title":"Inj. Prev."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1543","DOI":"10.1515\/bejeap-2013-0122","article-title":"Designated driver service availability and its effects on drunk driving behaviors","volume":"14","author":"Chung","year":"2014","journal-title":"BE J. Econ. Anal. Policy"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1146\/annurev.soc.26.1.341","article-title":"Nonstandard employment relations: Part-time, temporary and contract work","volume":"26","author":"Kalleberg","year":"2000","journal-title":"Annu. Rev. Sociol."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1080\/14616696.2018.1473627","article-title":"Part-time work and gender inequality in Europe: A comparative analysis of satisfaction with work\u2013life balance","volume":"21","author":"Beham","year":"2019","journal-title":"Eur. Soc."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1080\/13668803.2019.1581138","article-title":"When does part-time work relate to less work-life conflict for parents? Moderating influences of workplace support and gender in the Netherlands, Sweden and the United Kingdom","volume":"22","author":"Evertsson","year":"2019","journal-title":"Community Work. Fam."},{"key":"ref_7","unstructured":"Global Stories (2021, October 21). The Story between a Valet Driver and a Drunk Lady. Available online: https:\/\/www.sohu.com\/a\/496253639_121247013."},{"key":"ref_8","unstructured":"Institute of SME (2021, December 11). Improve the Riding Safety of the Valet driver! Didi Releases Orange Latern 2.0. Available online: https:\/\/www.sohu.com\/a\/437565584_120510457."},{"key":"ref_9","unstructured":"Finance China (2021, January 06). Didi Valet Driving Launched a New Equipment Light Package to further Improve the Driver\u2019s Riding Safety. Available online: http:\/\/finance.china.com.cn\/roll\/20210106\/5470326.shtml."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1080\/07448489909595640","article-title":"The use of designated drivers by US college students: A national study","volume":"47","author":"DeJong","year":"1999","journal-title":"J. Am. Coll. Health"},{"key":"ref_11","first-page":"256","article-title":"Public Acceptance of Designated Driver Services for Alcohol-Drinking","volume":"5","author":"Phan","year":"2018","journal-title":"Asian Transp. Stud."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Jou, R.C., and Syu, L.W. (2021). Drunk drivers\u2019 willingness to use and to pay for designated drivers. Sustainability, 13.","DOI":"10.3390\/su13105362"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/S0022-4375(03)00008-2","article-title":"Do the designated drivers of college students stay sober?","volume":"34","author":"Timmerman","year":"2003","journal-title":"J. Saf. Res."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1760","DOI":"10.3390\/ijerph6061760","article-title":"Hazards faced by young designated drivers: In-car risks of driving drunken passengers","volume":"6","author":"Rothe","year":"2009","journal-title":"Int. J. Environ. Res. Public Health"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1080\/15389588.2013.810334","article-title":"Characteristics of designated drivers and their passengers from the 2007 National Roadside Survey in the United States","volume":"15","author":"Bergen","year":"2014","journal-title":"Traffic Inj. Prev."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"103669","DOI":"10.1016\/j.trc.2022.103669","article-title":"On-demand valet charging for electric vehicles: Economic equilibrium, infrastructure planning and regulatory incentives","volume":"140","author":"Lai","year":"2022","journal-title":"Transp. Res. Part Emerg. Technol."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/j.trb.2021.09.006","article-title":"A two-stage ambiguous stochastic program for electric vehicle charging station location problem with valet charging service","volume":"153","author":"Li","year":"2021","journal-title":"Transp. Res. B Methodol."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/s12469-011-0038-9","article-title":"Implementing a branch and price and cut method for the airline crew pairing optimization problem","volume":"3","author":"Wesselmann","year":"2011","journal-title":"Public Transp."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/s10100-017-0489-4","article-title":"Computing strong lower and upper bounds for the integrated multiple-depot vehicle and crew scheduling problem with branch-and-price","volume":"27","author":"Kis","year":"2019","journal-title":"Cent. Eur. J. Oper. Res."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/j.trb.2018.04.008","article-title":"Vehicle and crew scheduling for flexible bus transportation systems","volume":"112","author":"Boyer","year":"2018","journal-title":"Transp. Res. B Methodol."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"105268","DOI":"10.1016\/j.cor.2021.105268","article-title":"Solution approaches for integrated vehicle and crew scheduling with electric buses","volume":"132","author":"Perumal","year":"2021","journal-title":"Comput. Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1016\/j.ejor.2015.06.026","article-title":"Network repair crew scheduling and routing for emergency relief distribution problem","volume":"248","author":"Duque","year":"2016","journal-title":"Eur. J. Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1016\/j.ejor.2011.10.048","article-title":"The home care crew scheduling problem: Preference-based visit clustering and temporal dependencies","volume":"219","author":"Rasmussen","year":"2012","journal-title":"Eur. J. Oper. Res."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/s10479-007-0170-8","article-title":"The dial-a-ride problem: Models and algorithms","volume":"153","author":"Cordeau","year":"2007","journal-title":"Ann. Oper. Res."},{"key":"ref_25","first-page":"89","article-title":"The Dial-a-Ride Problem (DARP): Variants, modeling issues and algorithms","volume":"2","author":"Cordeau","year":"2003","journal-title":"4OR"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1016\/j.trb.2018.02.001","article-title":"A survey of dial-a-ride problems: Literature review and recent developments","volume":"111","author":"Ho","year":"2018","journal-title":"Transp. Res. B Methodol."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1016\/S0191-2615(02)00045-0","article-title":"A tabu search heuristic for the static multi-vehicle dial-a-ride problem","volume":"37","author":"Cordeau","year":"2003","journal-title":"Transp. Res. B Methodol."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1287\/opre.1060.0283","article-title":"A branch-and-cut algorithm for the dial-a-ride problem","volume":"54","author":"Cordeau","year":"2006","journal-title":"Oper. Res."},{"key":"ref_29","first-page":"258","article-title":"Models and branch-and-cut algorithms for pickup and delivery problems with time windows","volume":"49","author":"Ropke","year":"2007","journal-title":"Netw. Int. J."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/s10288-006-0018-0","article-title":"An effective and fast heuristic for the dial-a-ride problem","volume":"5","author":"Calvo","year":"2007","journal-title":"4OR"},{"key":"ref_31","first-page":"227","article-title":"A heuristic two-phase solution approach for the multi-objective dial-a-ride problem","volume":"54","author":"Parragh","year":"2009","journal-title":"Netw. Int. J."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"127","DOI":"10.15837\/ijccc.2009.2.2420","article-title":"Application of genetic algorithms for the DARPTW problem","volume":"4","author":"Cubillos","year":"2009","journal-title":"Int. J. Comput. Commun. Control."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1129","DOI":"10.1016\/j.cor.2009.10.003","article-title":"Variable neighborhood search for the dial-a-ride problem","volume":"37","author":"Parragh","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1721837.1721857","article-title":"Dial a ride from k-forest","volume":"6","author":"Gupta","year":"2010","journal-title":"ACM Trans. Algorithms TALG"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1435","DOI":"10.1016\/j.cor.2010.12.014","article-title":"Optimization of occupancy rate in dial-a-ride problems via linear fractional column generation","volume":"38","author":"Garaix","year":"2011","journal-title":"Comput. Oper. Res."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1121","DOI":"10.1016\/j.engappai.2012.03.012","article-title":"A multi-objective simulated annealing for the multi-criteria dial a ride problem","volume":"25","author":"Zidi","year":"2012","journal-title":"Eng. Appl. Artif. Intell."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1016\/j.trb.2013.07.014","article-title":"A granular tabu search algorithm for the dial-a-ride problem","volume":"56","author":"Kirchler","year":"2013","journal-title":"Transp. Res. B Methodol."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/j.ejor.2012.09.008","article-title":"Synchronized dial-a-ride transportation of disabled passengers at airports","volume":"225","author":"Reinhardt","year":"2013","journal-title":"Eur. J. Oper. Res."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/j.trb.2014.05.007","article-title":"Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots","volume":"67","author":"Braekers","year":"2014","journal-title":"Transp. Res. B Methodol."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"700","DOI":"10.1002\/atr.1296","article-title":"A revised branch-and-price algorithm for dial-a-ride problems with the consideration of time-dependent travel cost","volume":"49","author":"Hu","year":"2015","journal-title":"J. Adv. Transp."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1287\/trsc.2014.0520","article-title":"The dial-a-ride problem with split requests and profits","volume":"49","author":"Parragh","year":"2015","journal-title":"Transp. Sci."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1287\/trsc.2014.0531","article-title":"Effective handling of dynamic time windows and its application to solving the dial-a-ride problem","volume":"49","author":"Gschwind","year":"2015","journal-title":"Transp. Sci."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/j.trb.2016.09.010","article-title":"A multi-period dial-a-ride problem with driver consistency","volume":"94","author":"Braekers","year":"2016","journal-title":"Transp. Res. B Methodol."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.omega.2016.08.008","article-title":"A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare","volume":"70","author":"Detti","year":"2017","journal-title":"Omega"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.cor.2016.12.008","article-title":"A hybrid genetic algorithm for the heterogeneous dial-a-ride problem","volume":"81","author":"Masmoudi","year":"2017","journal-title":"Comput. Oper. Res."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"480","DOI":"10.1287\/trsc.2018.0837","article-title":"Adaptive large neighborhood search with a constant-time feasibility test for the dial-a-ride problem","volume":"53","author":"Gschwind","year":"2019","journal-title":"Transp. Sci."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1287\/trsc.2015.0651","article-title":"An exact approach for a variant of the pollution-routing problem","volume":"51","author":"Dabia","year":"2017","journal-title":"Transp. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/5\/224\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:24:19Z","timestamp":1760124259000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/5\/224"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,27]]},"references-count":47,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2023,5]]}},"alternative-id":["a16050224"],"URL":"https:\/\/doi.org\/10.3390\/a16050224","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2023,4,27]]}}}