A mixed-integer linear programming approach to the optimization of event-bus schedules: a scheduling application in the tourism sector

This paper deals with “The Enchanted Journey,” which is a daily event tour booked by Bollywood-film fans. During the tour, the participants visit original sites of famous Bollywood films at various locations in Switzerland; moreover, the tour includes stops for lunch and shopping. Each day, up to five buses operate the tour. For operational reasons, however, two or more buses cannot stay at the same location simultaneously. Further operative constraints include time windows for all activities and precedence constraints between some activities. The planning problem is how to compute a feasible schedule for each bus. We implement a two-step hierarchical approach. In the first step, we minimize the total waiting time; in the second step, we minimize the total travel time of all buses. We present a basic formulation of this problem as a mixed-integer linear program. We enhance this basic formulation by symmetry-breaking constraints, which reduces the search space without loss of generality. We report on computational results obtained with the Gurobi Solver. Our numerical results show that all relevant problem instances can be solved using the basic formulation within reasonable CPU time, and that the symmetry-breaking constraints reduce that CPU time considerably.

Proposals for Specific Activities of the Basic Mandate and Priority Action Projects, 2nd round 2005: Documentation for the ESAPP Advisory Board Meeting of June 15th, 2005

Budget frame-figures for 2nd half 2005; priority listing of proposals for PAP 2nd round 2005; evaluation sheets of approved, revised and rejected proposals for Specific Activities of the BM and PAP.

Annual Planning for the Basic Mandate and Proposals for Priority Action Projects, 1st round 2005

Budget frame-figures for 2005; annual planning for the BM 2005; priority listing of proposals for PAP 2005; evaluation sheets of approved, postponed and rejected proposals for the BM and PAP.

Proposals for Priority Action Projects, second round 2004

Budget frame-figures for 2nd half of 2004; priority listing of proposals for PAP 2nd round 2004; evaluation sheets of approved, revised and rejected proposals for PAP.

A note on the selection of priority rules in software packages for project management

Various software packages for project management include a procedure for resource-constrained scheduling. In several packages, the user can influence this procedure by selecting a priority rule. However, the resource-allocation methods that are implemented in the procedures are proprietary information; therefore, the question of how the priority-rule selection impacts the performance of the procedures arises. We experimentally evaluate the resource-allocation methods of eight recent software packages using the 600 instances of the PSPLIB J120 test set. The results of our analysis indicate that applying the default rule tends to outperform a randomly selected rule, whereas applying two randomly selected rules tends to outperform the default rule. Applying a small set of more than two rules further improves the project durations considerably. However, a large number of rules must be applied to obtain the best possible project durations.