research-article

A genetic algorithm based column generation method for multi-depot electric bus vehicle scheduling

Authors:

Congcong Guo,

Chunlu Wang,

Xingquan ZuoAuthors Info & Claims

GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Pages 367 - 368

https://doi.org/10.1145/3319619.3321991

Published: 13 July 2019 Publication History

Get Access

Abstract

In this paper, we study a multi-depot electric bus vehicle scheduling problem (MD-EVSP) and propose a genetic algorithm based column generation approach (GA-CG) for it. In GA-CG, a column refers to a driving plan of a vehicle. CG first generates a set of candidate columns. Then, a GA is used to select a subset of candidate columns from the column set to form the final solution. Experiments show that GA-CG can effectively solve MD-EVSP and runs much fast than branch and price algorithm.

References

[1]

A. Pepin, D. Desaulniers, A. Hertz, D. Huisman. 2009. A comparison of five heuristics for the multiple depot vehicle scheduling problem. Journal of Scheduling 12, 1 (2009), 17--30.

Digital Library

Google Scholar

[2]

J. Q. Li. 2013. Transit bus scheduling with limited energy. Transportation Science 48, 4 (2013), 521--539.

Digital Library

Google Scholar

[3]

G. Desaulniers, J. Desrosiers, M. M. Solomon (Eds.). 2010. Column generation. Springer-Verlag New York Inc.

Google Scholar

[4]

D. Feillet, P. Dejax, M. Gendreau, et al. 2004. An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks 44, 3(2004), 216--229.

Crossref

Google Scholar

[5]

F. Duan. 1994. SPFA Fast Algorithm for Shortest Paths. Journal of Southwest Jiaotong University 29, 2(1994), 207--212.

Google Scholar

Cited By

View all

章炎(2024)Multi-Objective Bus Vehicle Scheduling Based on Super Spatiotemporal NetworkOperations Research and Fuzziology10.12677/orf.2024.14657214:06(726-741)Online publication date: 2024
https://doi.org/10.12677/orf.2024.146572
Seman LRigo CCamponogara EBezerra ECoelho L(2023)Explainable column-generation-based genetic algorithm for knapsack-like energy aware nanosatellite task schedulingApplied Soft Computing10.1016/j.asoc.2023.110475144(110475)Online publication date: Sep-2023
https://doi.org/10.1016/j.asoc.2023.110475
Bie YHao MGuo M(2021)Optimal Electric Bus Scheduling Based on the Combination of All-Stop and Short-Turning StrategiesSustainability10.3390/su1304182713:4(1827)Online publication date: 8-Feb-2021
https://doi.org/10.3390/su13041827
Show More Cited By

Index Terms

A genetic algorithm based column generation method for multi-depot electric bus vehicle scheduling

Recommendations

Genetic Algorithm for Optimal Charge Scheduling of Electric Vehicle Fleet
NISS '19: Proceedings of the 2nd International Conference on Networking, Information Systems & Security

Electric Vehicles (EV) are gradually conquering more roads and replacing pollutant conventional vehicles. They seem to be used to store energy in clean and smart grids to mitigate greenhouse gas emissions and eliminate harmful peak loads. This paper ...
A Genetic Algorithm for Scheduling Electric Vehicle Charging
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

This paper addresses a problem motivated by a real life environment, in which we have to schedule the charge of electric vehicles in a parking, subject to a set of constraints, with the objective of minimizing the total tardiness. We consider both the ...
Column generation based heuristic framework for the multiple-depot vehicle type scheduling problem

This is the first time that column generation is directly applied to the MDVTSP.The development of algorithms to speedup the CG solution process.The design of a random instance generator for the MDVTSP. The multiple-depot vehicle-type scheduling problem ...

Comments

Information & Contributors

Information

Published In

GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion

July 2019

2161 pages

ISBN:9781450367486

DOI:10.1145/3319619

Editor:
Manuel López-Ibáñez
University of Manchester, UK
,
General Chairs:
Anne Auger
Inria and Ecole Polytechnique, France
,
Thomas Stützle
IRIDIA, Université libre de Bruxelles Belgium

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '19

Sponsor:

SIGEVO

GECCO '19: Genetic and Evolutionary Computation Conference

July 13 - 17, 2019

Prague, Czech Republic

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
200
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)1

Reflects downloads up to 06 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

章炎(2024)Multi-Objective Bus Vehicle Scheduling Based on Super Spatiotemporal NetworkOperations Research and Fuzziology10.12677/orf.2024.14657214:06(726-741)Online publication date: 2024
https://doi.org/10.12677/orf.2024.146572
Seman LRigo CCamponogara EBezerra ECoelho L(2023)Explainable column-generation-based genetic algorithm for knapsack-like energy aware nanosatellite task schedulingApplied Soft Computing10.1016/j.asoc.2023.110475144(110475)Online publication date: Sep-2023
https://doi.org/10.1016/j.asoc.2023.110475
Bie YHao MGuo M(2021)Optimal Electric Bus Scheduling Based on the Combination of All-Stop and Short-Turning StrategiesSustainability10.3390/su1304182713:4(1827)Online publication date: 8-Feb-2021
https://doi.org/10.3390/su13041827
Bie YJi JWang XQu X(2021)Optimization of electric bus scheduling considering stochastic volatilities in trip travel time and energy consumptionComputer-Aided Civil and Infrastructure Engineering10.1111/mice.12684Online publication date: 4-May-2021
https://doi.org/10.1111/mice.12684
Alvo MAngulo GKlapp M(2021)An exact solution approach for an electric bus dispatch problemTransportation Research Part E: Logistics and Transportation Review10.1016/j.tre.2021.102528156(102528)Online publication date: Dec-2021
https://doi.org/10.1016/j.tre.2021.102528
Stumpe MRößler DSchryen GKliewer N(2021)Study on sensitivity of electric bus systems under simultaneous optimization of charging infrastructure and vehicle schedulesEURO Journal on Transportation and Logistics10.1016/j.ejtl.2021.100049(100049)Online publication date: Sep-2021
https://doi.org/10.1016/j.ejtl.2021.100049
Rivera GCisneros LSánchez-Solís PRangel-Valdez NRodas-Osollo J(2020)Genetic Algorithm for Scheduling Optimization Considering Heterogeneous Containers: A Real-World Case StudyAxioms10.3390/axioms90100279:1(27)Online publication date: 4-Mar-2020
https://doi.org/10.3390/axioms9010027

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Genetic Algorithm for Optimal Charge Scheduling of Electric Vehicle Fleet

A Genetic Algorithm for Scheduling Electric Vehicle Charging

Column generation based heuristic framework for the multiple-depot vehicle type scheduling problem

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations