Article Preview
Top1. Introduction
The management of planning problems confronting logistics service providers frequently involves complex decisions. For more than four decades now the Bus Driver Allocation Problem (BDAP) in the Road Passenger Transport Company (RPTC) has retained the attention of the Management and Operations Research community since bus drivers management is extremely complex and may generate many problems that hinder the smooth operation, influencing the total transport company’s operations profit. Therefore, RPTC considers that the efficient management of their drivers is a question of the highest economic relevance. Many studies have tried to solve the BDAP problem either using optimization methods or complex type of heuristic methods. Unfortunately, the exact numerical solution of the associated large scale combinatorial optimization problem is very difficult to obtain. Early rules of thumb have been quickly overrun by the size of the practical problems encountered (hundreds or thousands of drivers to be assigned to at least as many duties) and by the complexity of the set of constraints to be satisfied, leading very often to poor performance solutions. More recently, with the enhancement of computer performances, optimization approaches have been proposed to solve this problem: mathematical programming methods (large scale linear programming and integer programming techniques) (Desrochers, Gilbert, Sauve, & Soumis, 1992; Curtis, Smith, & Wren, 1999; Smith, Layfield, & Wren, 2000), artificial intelligence methods (logical programming, simulated annealing, neural networks, fuzzy logic and genetic algorithms) as well as heuristic approaches and their respective combinations (Brusco, 1993; Clement & Wren, 1995; Beasley, 1996; Sengoku & Yoshihara, 1998; Yoshihara & Sengoku, 2000; Aickelin & Dowsland, 2003). Many studies refer to the BDAP which is a static decision problem, based on a monthly table of trips, and devoted exclusively to the minimization of RPTC operations costs. This problem is in general split in two sub problems: the first problem consists to generate the set of trips (or rotations) which cover optimally all the scheduled duties. A trip is composed of a set of duties that start and take end in the same base. The second problem is called BDAP where the retained trips are assigned to the drivers.
In this paper, we introduce the BDAP as a bi-criterion decision problem where the main decision criterion is the drivers operations cost of the RPTC and the secondary decision criterion is relative to the drivers overall degree of satisfaction. A set of hard and soft constraints are considered while solving the BDAP. The solution produced some knowledge which is used with the previous satisfaction level reached in the latest scheduling in order to get the current individual satisfaction level for the next planning by applying a classification process. The presence of multiple objectives in a problem, gives rise to a set of Pareto-optimal solutions. Several approach proposed in literature aims to detect the Pareto optimal solutions and capture the shape of the Pareto front. Over the past decade, a number of multi-objective evolutionary algorithms have been suggested (Horn, Nafploitis, & Goldberg, 1994; Srinivas & Deb, 1995; Deb, 2001). The primary reason for this is their ability to find multiple Pareto-optimal solutions in one single simulation run. Evolutionary Algorithms (EA) are good candidate to multiple objective optimization problems due to their abilities to search simultaneously for multiple Pareto-optimal solutions and, perform better global search of the search space. In recent years, many evolutionary techniques for multi-objective optimization have been proposed (Deb, 2001). Several multi-objective evolutionary algorithms are presented in literature such as: Non-dominated Sorting Genetic Algorithm (Zitzler, Deb & Thiele, 2000; Deb, Pratap, Agarwal, & Meyarivan, 2002), Multi-Objective Particle Swarm Optimization, and Multi-Objective Bacteria Foraging Optimization algorithm.