A Two-Stage Approach With a Departure Time Based Solution Representation for Electric Bus Vehicle Scheduling
Vehicle scheduling problem (VSP) in public transit refers to arranging a fleet of vehicles to make vehicles’ departure times coincide with the times in given bus timetables. It is vital for bus enterprises to ensure the service quality and save operational cost. Due to the limited driving...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2022-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9924158/ |
| _version_ | 1811256568696537088 |
|---|---|
| author | Yahong Liu Chunyang Cheng Hongyi Shi Xingquan Zuo Shaohua Chen |
| author_facet | Yahong Liu Chunyang Cheng Hongyi Shi Xingquan Zuo Shaohua Chen |
| author_sort | Yahong Liu |
| collection | DOAJ |
| description | Vehicle scheduling problem (VSP) in public transit refers to arranging a fleet of vehicles to make vehicles’ departure times coincide with the times in given bus timetables. It is vital for bus enterprises to ensure the service quality and save operational cost. Due to the limited driving range and charging requirements of electric vehicles, how to efficiently schedule electric vehicles is a challenging task with the popularization of electric bus vehicles. In this paper, we propose a two-stage solution approach (SA-LS) combining a simulated annealing (SA) and a local search (LS) for an electric vehicle scheduling problem (EVSP) in public transport. This approach is based on a novel solution coding that represents a scheduling solution by departure times of a fleet of vehicles. The decoding procedure considers limited driving range and recharging time of electric vehicles. The SA is used to find a set of solutions able to be potentially improved by LS. The LS combined with a departure-time adjustment procedure (DTAP) is devised to improve the solutions found by SA. Evaluation functions are devised separately for SA and LS to guide their search. The proposed approach is applied to real world vehicle scheduling problem of three bus lines in Qingdao city, China. Experiments show that SA-LS is able to generate high-quality scheduling solutions within short computational time. |
| first_indexed | 2024-04-12T17:43:23Z |
| format | Article |
| id | doaj.art-4531595fe62548c1bd3d1a53cc5bc183 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-04-12T17:43:23Z |
| publishDate | 2022-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-4531595fe62548c1bd3d1a53cc5bc1832022-12-22T03:22:45ZengIEEEIEEE Access2169-35362022-01-011011279911281110.1109/ACCESS.2022.32155929924158A Two-Stage Approach With a Departure Time Based Solution Representation for Electric Bus Vehicle SchedulingYahong Liu0Chunyang Cheng1Hongyi Shi2https://orcid.org/0000-0002-4846-1688Xingquan Zuo3https://orcid.org/0000-0001-9580-1182Shaohua Chen4Key Laboratory of Trustworthy Distributed Computing and Service, School of Computer Science, Ministry of Education, Beijing University of Posts and Telecommunications, Beijing, ChinaKey Laboratory of Trustworthy Distributed Computing and Service, School of Computer Science, Ministry of Education, Beijing University of Posts and Telecommunications, Beijing, ChinaKey Laboratory of Trustworthy Distributed Computing and Service, School of Computer Science, Ministry of Education, Beijing University of Posts and Telecommunications, Beijing, ChinaKey Laboratory of Trustworthy Distributed Computing and Service, School of Computer Science, Ministry of Education, Beijing University of Posts and Telecommunications, Beijing, ChinaKey Laboratory of Trustworthy Distributed Computing and Service, School of Computer Science, Ministry of Education, Beijing University of Posts and Telecommunications, Beijing, ChinaVehicle scheduling problem (VSP) in public transit refers to arranging a fleet of vehicles to make vehicles’ departure times coincide with the times in given bus timetables. It is vital for bus enterprises to ensure the service quality and save operational cost. Due to the limited driving range and charging requirements of electric vehicles, how to efficiently schedule electric vehicles is a challenging task with the popularization of electric bus vehicles. In this paper, we propose a two-stage solution approach (SA-LS) combining a simulated annealing (SA) and a local search (LS) for an electric vehicle scheduling problem (EVSP) in public transport. This approach is based on a novel solution coding that represents a scheduling solution by departure times of a fleet of vehicles. The decoding procedure considers limited driving range and recharging time of electric vehicles. The SA is used to find a set of solutions able to be potentially improved by LS. The LS combined with a departure-time adjustment procedure (DTAP) is devised to improve the solutions found by SA. Evaluation functions are devised separately for SA and LS to guide their search. The proposed approach is applied to real world vehicle scheduling problem of three bus lines in Qingdao city, China. Experiments show that SA-LS is able to generate high-quality scheduling solutions within short computational time.https://ieeexplore.ieee.org/document/9924158/Electric vehiclebus vehicle schedulingsimulated annealinglocal search |
| spellingShingle | Yahong Liu Chunyang Cheng Hongyi Shi Xingquan Zuo Shaohua Chen A Two-Stage Approach With a Departure Time Based Solution Representation for Electric Bus Vehicle Scheduling IEEE Access Electric vehicle bus vehicle scheduling simulated annealing local search |
| title | A Two-Stage Approach With a Departure Time Based Solution Representation for Electric Bus Vehicle Scheduling |
| title_full | A Two-Stage Approach With a Departure Time Based Solution Representation for Electric Bus Vehicle Scheduling |
| title_fullStr | A Two-Stage Approach With a Departure Time Based Solution Representation for Electric Bus Vehicle Scheduling |
| title_full_unstemmed | A Two-Stage Approach With a Departure Time Based Solution Representation for Electric Bus Vehicle Scheduling |
| title_short | A Two-Stage Approach With a Departure Time Based Solution Representation for Electric Bus Vehicle Scheduling |
| title_sort | two stage approach with a departure time based solution representation for electric bus vehicle scheduling |
| topic | Electric vehicle bus vehicle scheduling simulated annealing local search |
| url | https://ieeexplore.ieee.org/document/9924158/ |
| work_keys_str_mv | AT yahongliu atwostageapproachwithadeparturetimebasedsolutionrepresentationforelectricbusvehiclescheduling AT chunyangcheng atwostageapproachwithadeparturetimebasedsolutionrepresentationforelectricbusvehiclescheduling AT hongyishi atwostageapproachwithadeparturetimebasedsolutionrepresentationforelectricbusvehiclescheduling AT xingquanzuo atwostageapproachwithadeparturetimebasedsolutionrepresentationforelectricbusvehiclescheduling AT shaohuachen atwostageapproachwithadeparturetimebasedsolutionrepresentationforelectricbusvehiclescheduling AT yahongliu twostageapproachwithadeparturetimebasedsolutionrepresentationforelectricbusvehiclescheduling AT chunyangcheng twostageapproachwithadeparturetimebasedsolutionrepresentationforelectricbusvehiclescheduling AT hongyishi twostageapproachwithadeparturetimebasedsolutionrepresentationforelectricbusvehiclescheduling AT xingquanzuo twostageapproachwithadeparturetimebasedsolutionrepresentationforelectricbusvehiclescheduling AT shaohuachen twostageapproachwithadeparturetimebasedsolutionrepresentationforelectricbusvehiclescheduling |