Browsing by Author "Paias, Ana"
Now showing 1 - 6 of 6
Results Per Page
Sort Options
- A decompose-and-fix heuristic based on multi-commodity flow models for driver rostering with days-off patternPublication . Mesquita, Marta; Moz, Margarida; Paias, Ana; Pato, Margarida VazFacing severe budgetary constraints, public transport companies are forced to efficiently manage staff, one of the most expensive resources. The driver rostering problem in a public transit company consists of defining rosters, that is, assigning daily crew duties to the company’s drivers for a pre-defined time horizon, ensuring transport demand in a specific area, at low operating costs, while complying with legal restrictions and agreements between the company and the driver unions. The objective of this paper is the study of mathematical models and optimization techniques that lead to new computational tools able to solve the bus driver rostering problem with days-off patterns by producing solutions that increase efficiency and reduce operating costs, while improving or maintaining the service quality and balancing the drivers’ workload. Three mixed integer linear programming formulations are presented and compared from a theoretical point of view: an assignment/cover model, a multi-commodity flow model and a new multi-commodity f low/assignment model. Based on a hierarchy of the decisions made during the resolution of the problem, a new decompose-and-fix heuristic is developed by exploring the underlying structure of the multi-commodity flow models. The heuristic solves the sequence of sub-problems identified by the hierarchy, while fixing or bounding the value of some variables to incorporate previous decisions. Computational experiments were carried out with instances, derived from real world data and from benchmark data, characterized by a days-off pattern in use at two Portuguese public bus transport companies. Computational results confirm the good performance of the decompose-and-fix heuristic.
- A decomposition approach for the integrated vehicle-crew-roster problem with days-off patternPublication . Mesquita, Marta; Moz, Margarida; Paias, Ana; Pato, Margarida VazThe integrated vehicle-crew-roster problem with days-off pattern aims to simultaneously determine minimum cost vehicle and daily crew schedules that cover all timetabled trips and a minimum cost roster covering all daily crew duties according to a pre-defined days-off pattern. This problem is formulated as a new integer linear programming model and is solved by a heuristic approach based on Benders decom- position that iterates between the solution of an integrated vehicle-crew scheduling problem and the solution of a rostering problem. Computational experience with data from two bus companies in Portugal and data from benchmark vehicle scheduling instances shows the ability of the approach for producing a variety of solutions within reason able computing times as well as the advantages of integrating the three problems.
- A decomposition approach to the integrated vehicle-crew-rostering problemPublication . Mesquita, Marta; Moz, Margarida; Paias, Ana; Pato, Margarida VazThe problem addressed in this paper is the integrated vehicle-crew-rostering problem (VCRP) aiming to define the schedules for the buses and the rosters for the drivers of a public transit company. The VCRP is described by a bi-objective mixed binary linear programming model with one objective function aggregating vehicle and crew scheduling costs and the other the rostering features. The VCRP is solved by a heuristic approach based on Benders decomposition where the master problem is partitioned into daily integrated vehicle-crew scheduling problems and the sub-problem is a rostering problem. Computational experience with data from a bus company in Lisbon shows the ability of the decomposition approach for producing a variety of potentially efficient solutions for the VCRP within low computing times.
- A network flow-based algorithm for bus driver rerosteringPublication . Paias, Ana; Mesquita, Marta; Moz, Margarida; Pato, Margarida VazBus driver rostering generates the work plan for a pool of drivers during a planning period of predefned length. This plan, called the roster, must consider the balance between the pressure of costs, the provision of a service of high quality, labour agreements, and the goodwill of the workers. The bus driver rerostering problem occurs during real-time operational planning, when unexpected events—such as non-planned absences of drivers—disrupt the roster. To reconstruct a roster which is originally built in a context of days of schedules for drivers, we propose a reactive methodology based on a multicommodity fow assignment mixed integer linear programming model. The objective is to minimise the number of depot drivers who are assigned to drive and the number of postponed days of, as well as the dissimilarity between the reconstructed and the original roster and the balancing of the workload. The proposed algorithm enables the disrupted roster to be reconstructed at the expense of a relatively small number of changes in drivers’ work and rest periods, while, at the same time, controlling the dimension of the multicommodity fow network. Computational experience based on real-life based instances revealed that the algorithm has the ability to produce reconstructed rosters with few changes to the drivers’ original work assignment, in a short CPU time.
- A new model for the integrated vehicle-crew-rostering problem and a computational study on rostersPublication . Mesquita, Marta; Moz, Margarida; Paias, AnaOperational planning within public transit companies has been extensively tackled but still remains a challenging area for operations research models and techniques. This phase of the planning process comprises vehicle scheduling, crew-scheduling and rostering problems. In this paper, a new integer mathematical formulation to describe the integrated vehicle-crew-rostering problem is presented. The method proposed to obtain feasible solutions for this binary non-linear multi-objective optimization problem is a sequential algorithm considered within a preemptive goal programming framework that gives a higher priority to the integrated vehicle-crew-scheduling goal and a lower priority to the driver rostering goals. A heuristic approach is developed where the decision maker can choose from different vehicle-crew schedules and rosters, while respecting as much as possible management’s interests and drivers’ preferences. An application to real data of a Portuguese bus company shows the influence of vehicle-crew-scheduling optimization on rostering solutions
- Solving Public Transit Scheduling ProblemsPublication . Mesquita, Marta; Moz, Margarida; Paias, Ana; Paixão, José; Pato, Margarida Vaz; Respício, AnaOperational planning within public transit companies has been extensively tackled but still remains a challenging area for operations research models and techniques. This phase of the planning process comprises vehicle scheduling, crew scheduling and rostering problems. In this paper, a new integer mathematical formulation to describe the integrated vehicle-crew-rostering problem is presented. The method proposed to solve this multi-objective problem is a sequential algorithm considered within a preemptive goal programming framework that starts from the solution of an integrated vehicle and crew scheduling problem and ends with the solution of a driver rostering problem. Feasible solutions for the vehicle and crew scheduling problem are obtained by combining a column generation scheme with a branch-and-bound method. These solutions are the input of the rostering problem, which is tackled through a mixed binary linear programming approach. An application to real data of a Portuguese bus company is reported and shows the importance of integrating the three scheduling problems.