مسئله ی مسیر یابی اتوبوس شهری در مورد تونس توسط الگوریتم کلونی مورچه مصنوعی ترکیبی

The problem statement tackled in this paper is concentrated on the school bus routing problem (SBRP) in urban areas. This problem is a variant of the vehicle routing problem where we identify three simultaneous decisions that have to be made: determining the set of stops to visit, for each student which stop he should walk to and the latter case occurs when determining the routes visited with the chosen stops, so that the total traveled distance is minimized. Accordingly, to the Tunisian case study and the difficulty to solve it in a manual manner we resort to metaheuristic approaches. We have developed a hybrid evolutionary computation based on an artificial ant colony with a variable neighborhood local search algorithm. Empirically we demonstrate that our algorithm yields consistently better results.

Planning of urban public transport is important for companies, the local authority and users. For the company, the main objective of public transport planning is to optimize the operational cost on the entire network. Then, its profit, level of service and competitiveness can be improved. Vehicle fleet routing, frequencies, scheduling, vehicles affectation and correspondence synchronization are some examples of problems which can be resolved by public transport planning. Resolving these problems will be more difficult especially in an urban context because of demand diversification, urban activity multiplication and dispersed localization of activities and individuals. The Vehicle Routing Problem (VRP) [1] and [2] is extensively studied in research literature. It is one of the important methods which are adopted in public transport planning. It helps using efficiently the fleet of vehicles that must make a number of stops to pick up or deliver passengers or goods. Several studies have focused on this method and they applied it to resolve many transportation problems such as the inter-city routing problem [3], and the Urban Network Design Problem [4]. A survey of literature may be found in [5] and [6]. Planning of public transport is one of the issues which use the bus routing method. The School Bus Routing Problem (SBRP) can be presented as a problem of affectation of school buses in order to satisfy the demand of spatial distributed students from their residences to their school’s destination. It is one of the problems which can be solved by VRP and consists in planning bus transport supply in order to provide an efficient schedule for a fleet of school buses. Each of these buses must pick up students from bus stops and deliver them to their appropriate schools under many operational constraints such as the student transport demand, buses’ parking areas, the maximum capacity of a bus, the maximum trip time of a student in a bus, and the time window of a school. Taking into account these operational variables lead the company to make many decisions about bus stop selection, bus route generation, the adjustment to school time, and turning buses. The SBRP has received some attention in the last two decades. Park and Kim [7] summarized the assumptions, constraints, solutions and methods used by SBTP and others. The SBRP [8] and [9] is similar to VRP in several studies.1 It was proposed, for the first time, by Newton and Thomas [12]. Since this time, it has been developed leading to various approaches later described in literature. The latter approaches differ from each other regarding the problem of decomposition approach, constraints and solution algorithms. Then we distinguish the school-based and a home-based approach. In addition, several works have used the SBRP in order to optimize the school bus traffic under a single objective or multi-objectives in urban areas or/and rural area. Generally, the objective functions to be minimized are: the transportation cost which concern especially the company’s bus number needed for student transportation and the transportation time—the total travel time at pick-up points, and the total bus travel time. Many types of constraints have been integrated such as invariant or stochastic demand of passengers, limited bus capacities and total travel distance, efficiency, effectiveness, and equity of public service. Literature shows different optimizing programs to resolve the SBRP such as: the genetic algorithm, the Ant Colony Optimization algorithm, integer linear program and nonlinear integer program. Corberan et al. [13] used the SBRP in order to optimize the number of buses used for student transportation from the point of view of cost and to reduce the travel time that students spend in a bus. Li and Fu [14] formulated a multi-objective combinatorial optimization problem to resolve daily bus school transportation and to propose an efficient use of the school bus routes. The objectives adopted are: minimizing the number of buses needed to student transportation, the total travel time at pick-up points, and the total bus travel time. Spada et al. [15] developed three heuristics to resolve the SBRP with the hypothesis of a known transportation demand and they have compared them. Schittekat et al. [16] developed a mathematical model for a single-school bus routing problem. They adopted the school-based approach where the school is identical to a depot, and a route starts and ends at the school. Bektas and Elmastas [17] developed an integer linear program in order to solve the SBRP under capacity and distance constraints. Fügenschuh [18] proposed an integer programming model for the integrated coordination of the school starting time and the public bus services in rural areas. Recently, Kepaptsoglou, and Karlaftis [19] provide a review paper in the transportation literature given for the transit network Design Problem. This paper presents and reviews research on the Transit Network Design Problem based on the three distinctive parts of the Transit Network Design Problem setup: design objectives, operating environment parameters and solution approach. In Tunisia, transportation authorities have chosen to integrate school bus transportation in the public bus system and to make a strict regulation for public companies. Authorities regulate the price of school bus service but give important subsidies to help companies in order to respect public obligations, namely, efficiency, effectiveness and equity [20] and [14]. Despite these subsidies, budget deficits continue to increase and the school transportation costs become more important both for the ministry of transport as well as for the companies. Reducing these costs through operational variables becomes the main objective of Tunisian bus companies. In this context, we focus on the case of a transport Bus Company that operates in Great Tunis which serves main Tunisian cities and transports an important number of students. The objective of this paper is to find some solutions in order to minimize the total number of buses required related to the service cost. The minimum number of buses kk (assume one bus for one route only) required to serve all points for a school. Evolution computation (EC) motivated by evolution in the real world, has become one of the most widely used techniques, because of its effectiveness and versatility. It maintains a set of solution, which evolves subject to selection and genetic operators (such as recombination and mutation). Each individual in the population receives a measure of its fitness, which is used to guide selection (e.g. [21]). Ant colony family is a type of metaheuristic which has attained interest during the last 5 years. Ant colony optimization (ACO) is a metaheuristic algorithm emulating the behavior of real ant colonies when they search for food from their nest to food sources. It has been observed in [22] that of available routes, ants find the shortest route to the food nest. We present a review of ant algorithms in [23]. Our contribution is twofold: our first original contribution brings in a variant of Routing Problems known as the Bus Routing Problem (BRP), with a major contribution, which the paper presents in the Tunisian case study. Second, a major contribution of the paper is the development of an efficient hybrid metaheuristic based on the AAC with high-quality solution produced. This paper aims to provide a hybrid metaheuristic based on an artificial ant colony with a variable neighborhood local search to plan the bus routing problem. The paper is organized in the following way: the details of the bus routing problem are described in Section 2. In Section 3 the solution methodology developed for solution is presented. In Section 4 our hybrid algorithm to solve the BRP is discussed. To test the effectiveness of the algorithm, numerical results are reported in Section 5. Section 6 presents our computational case study in Tunisia. And finally the conclusion is in Section 7.

In this paper we have introduced a new hybrid artificial ant colony to solve the urban bus routing problem on the Tunisian case. We presented an extended study of a novel hybrid approach to rank solutions in bus routing problem in the presence of a real case. We have shown that the variable neighborhood as local search improves the performance of the artificial ant colony. We have proposed and analyzed the performance of our new hybrid algorithm for solving the real bus routing problem of Great Tunis. From the experiments carried out here we conclude that the proposed methodology is able to solve the hard bus routing problem in this case study. The results show that the solution produced by our metaheuristic is highly dependent on the choice of the local search; here we have implemented the variable neighborhood search inside the artificial ant colony. Our approach is competitive when compared with the results of the bus network provided by those responsible in the TBCT in Great Tunis (Table 4).