List-graph colouring for multiple depot vehicle scheduling
Summary: This article addresses a multiple depot vehicle scheduling problem (MDVSP) arising in public transportation. The general problem consists in assigning vehicles to trips while minimising the number of scheduled vehicles and the operational costs. The MDVSP considered here takes into account heterogeneous types of vehicles with complex relations among them. This special feature matches well situations encountered in practice, but makes the problem particularly difficult. We introduce a new formulation based on list-graph colouring, from which an iterative tabu search is developed for vehicle minimisation. The approach is assessed on seven real-world benchmarks and yields highly satisfactory results in terms of solution quality and computation time.
- A graph coloring approach to the deployment scheduling and unit assignment problem
- scientific article; zbMATH DE number 1594564
- A graph coloring algorithm for large scale scheduling problems
- Scheduling Problems and Mixed Graph Colorings
- Graph multi-coloring for a job scheduling application
- scientific article; zbMATH DE number 7203465
- Vehicle scheduling on a graph revisited
- List-colourings of graphs
- scientific article; zbMATH DE number 1361557
- Plurigraph coloring and scheduling problems
This page was built for publication: List-graph colouring for multiple depot vehicle scheduling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q843401)
