In the Coach Trip with Shuttle Service Problem, passengers are picked up from bus stations and transported to a central hub. Two types vehicles are available: coaches and smaller shuttle-vehicles. While all coaches terminate at the central hub, the shuttles may transport passengers either to the central hub, also, or bring them to a bus stop (transfer point) from where they get picked up by a coach.
The objective of the problem is minimize the total costs of transporting all passengers to the hub while respecting all side constraints. Individual cost functions for the coaches and the shuttle-vehicles are given, and maximum driving times must be respected for all bus stops (obviously, this limits the total trip duration for the passengers waiting at bus stops and hence presents an important practical aspect). Besides, each vehicle has a capacity constraint on the maximum number of transported passengers.
VeRoLog Solver Challenge 2015
The problem definition goes back to the VeRoLog Solver Challenge 2015, an implementation challenge of the EURO Working Group on Vehicle Routing and Logistics Optimization. The background of this problem is a business application of the PTV Group, a Karlsruhe-based company specializing in transportation/logistics optimization and software services.
We employ techniques from Variable Neighborhood Search, combined with Iterated Local Search. On a lower level, efficient data-structures for solution representations have been studied: It is possible to show that any feasible alternative may be represented by a forest of directed trees. The latter significantly contributed to the effectiveness of our concept. Moreover, a visualization of the obtained solutions has been implemented.
Our contribution ranked first in this competition. Follow this link to a press release by the sponsor.
A complete description of our work and the source-code of the developed program have been made available to the public.
Related key publications
Martin Josef Geiger (2017):
On an effective approach for the coach trip with shuttle service problem of the VeRoLog solver challenge 2015.
Networks, Volume 69, Issue 3, May 2017, Pages 329–345.
[doi:10.1002/net.21733]
Martin Josef Geiger:
VeRoLog Solver Challenge 2015 – sourcecode of my contribution.
[doi:10.17632/662mtv6sd8.1]
Letzte Änderung: 26. November 2017