Multiobjective Metaheuristics for the Bus Driver Scheduling Problem

Lourenço, Helena R.; Paixão, José P.; Portugal, Rita
August 2001
Transportation Science;Aug2001, Vol. 35 Issue 3, p331
Academic Journal
We present new multiobjective metaheuristics for solving real-world crew scheduling problems in public bus transport companies. Since the crews of these companies are drivers, we will designate the problem as bus-driver scheduling. Crew scheduling problems are well known, and several mathematical programming-based techniques have been proposed to solve them, in particular, using the single-objective set-covering formulation. However, in practice, there exists the need to consider multiple objectives, some of them in conflict with each other; for example, the cost and service quality, implying also that alternative solution methods have to be developed. We propose multiobjective metaheuristics based on the tabu search and genetic algorithms. These metaheuristics also present some innovation features related with the structure of the crew scheduling problem that guide the search efficiently and enable them to find good solutions. Some of these new features can also be applied to the development of heuristics to other combinatorial optimization problems. A summary of computational results with real-data problems is presented. The methods have been successfully incorporated in the GIST Planning Transportation Systems and are actually used by several companies.


Related Articles

  • Multi-objective Model on Connection Time Optimization in Sea-rail Intermodal Transport. Qi Zhang; Hao Yang; Li Zhang // GSTF Journal of Engineering Technology;Jul2014, Vol. 3 Issue 1, p112 

    Container sea-rail intermodal transport operation needs to consider some special demands both in volume and time connection. That means container sea-rail intermodal transport is a type of demand responsive transport between railroad trains and marine ships, vice versa. It needs to operate...

  • A Unicast QoS Routing genetic algorithm Based on Multiple Attribute Decision Making. LI Zhi; CHEN Niansheng // International Journal of Advancements in Computing Technology;Dec2012, Vol. 4 Issue 22, p731 

    Wireless multimedia sensor networks (WMSNs)is a new kind of network which is competent in transferring voice, images, video and other information. It has a broad prospect of application in military, environmental monitoring, intelligent transportation and so on. As for multimedia applications...

  • Efficient Multiobjective Genetic Algorithm for Solving Transportation, Assignment, and Transshipment Problems. Zaki, Sayed A.; Mousa, Abd Allah A.; Geneedi, Hamdy M.; Elmekawy, Adel Y. // Applied Mathematics;Jan2012, Vol. 3 Issue 1, p92 

    This paper presents an efficient genetic algorithm for solving multiobjective transportation problem, assignment, and transshipment Problems. The proposed approach integrates the merits of both genetic algorithm (GA) and local search (LS) scheme. The algorithm maintains a finite-sized archive of...

  • Alternating Deadheading in Bus Route Operations. Furth, Peter G. // Transportation Science;Feb85, Vol. 19 Issue 1, p13 

    "Alternating dead heading" is an operating strategy for urban bus routes that have a directional imbalance in passenger demand in which some of the vehicles operating on a route deadhead (return empty) in the reverse direction while others return in service. By reducing average cycle time, dead...

  • Multi-Objective Optimization Algorithm for Job Shop Scheduling Problem in Discrete Manufacturing Enterprise. Lilan Liu; Xuewei Liu; Sen Wang; Wei Zhou; Gaiping Zhao // Applied Mechanics & Materials;2014, Vol. 741, p860 

    Job Shop scheduling should satisfy the constraints of time, order and resource. To solve this NP-Hard problem, multi-optimization for job shop scheduling problem (JSSP) in discrete manufacturing plant is researched. Objective of JSSP in discrete manufacturing enterprise was analyzed, and...

  • Differential search algorithm-based parametric optimization of electrochemical micromachining processes. Goswami, Debkalpa; Chakraborty, Shankar // International Journal of Industrial Engineering Computations;2014, Vol. 5 Issue 2, p41 

    Electrochemical micromachining (EMM) appears to be a very promising micromachining process for having higher machining rate, better precision and control, reliability, flexibility, environmental acceptability, and capability of machining a wide range of materials. It permits machining of...

  • Design environment for structural design: application to modern multideck ships. Zanic, V.; Andric, J.; Prebeg, P. // Proceedings of the Institution of Mechanical Engineers -- Part M;Mar2009, Vol. 223 Issue 1, p105 

    This paper presents a design environment capable of embedding multiple quality criteria for structural design and to provide the decision support problem (DSP) rationale for the concept design phase. The general mathematical model contains the analysis and the synthesis modules. The analysis...

  • Multicriteria Decision Mechanism CNSGA-AHP for the Automatic Test Task Scheduling Problem. Hui Lu; Ruiyao Niu; Jing Liu; Zheng Zhu // Information Technology Journal;2012, Vol. 11 Issue 10, p1449 

    Task scheduling problem is one of the key technologies for automatic test systems. This study proposes a novel and integrated multicriteria decision mechanism called the chaotic non-dominated sorting genetic algorithm plus analytic hierarchy process (CNSGA-AHP) for the automatic test task...

  • New Method for Optimal Location and Parameters Setting of UPFC Devices Using Multi-Criteria Optimization. Savic, Aleksandar S.; Stefanov, Predrag C. // International Review of Electrical Engineering;Jul/Aug2012, Vol. 7 Issue 4, p5051 

    This paper is proposing a new procedure for a simultaneous optimization of all the criteria that may influence the decision, while it is not necessary to compare the criteria, and therefore provides that no single criterion is favored over the others. Therefore, this procedure represents an...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics