The grid based method for local evaluations in bus line planning

In bus line planning a bus operator has to decide which bus stops will beserved in which order. This is a challenging optimization problem where theevaluation of a single possible solution is costly. Line planning is only one ofseveral steps in the public transport planning process[1]. In practice all thesesteps are executed sequentially, while they have a large impact on eachother.The integration of multiple planning steps is a topic of ongoing research [2, 3].During line planning a lot of simpli cations are made. Despite the existence ofextensive and accurate passenger routing models, only the most simple ones arebeing used. Even then, when solving very large networks a lot of cpu time isnecessary. To make it possible to tackle very large networks or to use these moreaccurate routing models or to integrate multiple planning steps, faster evaluationmethods are necessary [4, 5, 6].There are two con icting goals that are present in every model [5, 6]. Thepublic bus company wants to be as cost e ective as possible, while the passengerswant the best possible service. These two goals are either present in the objectivefunction or in one of the constraints. This means the passenger routing has to becalculated regardless of your objective function.The calculation of the passenger routes is the main contributor to the highevaluation cost[3]. Since a small change to the bus network can have a large impacton the passenger routes, it is not possible to directly calculate the result of thenew solution. But passenger routes that come close to a proposed change to thenetwork before the change is made, are more likely to be impacted by the change.This is the basic principle behind the grid based approach. To approximate thedistance to a change and to make several pre calculations possible, a xed grid isplaced over the network. When a change to the network needs to be evaluated,a cut of the network is constructed. This cut contains the grid cell in which thechange happened and all adjacent cells. Based on the previous passenger routing,the demand for this cut is recalculated. Passengers are assumed to enter and leaveeach cut at the same spot before and after the change. With a network cut andthe demand, the passenger routing inside the cut can be recalculated with anymethod like usual.In the experiments, the grid based method is inserted into an iterated local1search algorithm. After showing the base algorithm without the grid can competewith literature [4, 7], both the grid based and base algorithm are tested on Mumford'sbenchmark instances. The grid approach managed to do up to 20 timesas many evaluations per second as the same algorithm without local evaluation,with minimal loss of quality. On the larger instances, the use of more complexlocal search moves resulted in the best found solutions. The grid based approachalso scales nicely with problem size. The evaluation of single cut is independent ofproblem size, only the size of the cut is important. If the network is larger thereare simply more possible cuts, just like there are more possible improvementsthat need to be evaluated. The overhead costs also scale better with problem sizethan a full evaluation. Because of the many possible improvements, this overheadwill become less and less important when the network gets larger. The larger thenetwork, the more interesting it is to use the grid based approach.Note that it is not the intention of this research to play the "up the wall" game,but rather to contribute by developing a new and fast evaluation method. Themethod is designed to be exible and usable independent of the base algorithmor evaluation method used.

Jaar van publicatie:2020