Bus maintenance systems and maintenance scheduling: model formulations and solutions

This paper deals with the problem of scheduling bus maintenance activities. The scheduling of maintenance activities is an important component in bus transit operations planning process. The other components include network route design, setting timetables, scheduling vehicles, and assignment of drivers. This paper presents a mathematical programming approach to the problem. This approach takes as input a given daily operating schedule for all buses assigned to a depot along with available maintenance resources. It, then, attempts to design daily inspection and maintenance schedules for the buses that are due for inspection so as to minimize the interruptions in the daily bus operating schedule, and maximize the utilization of the maintenance facilities. Three integer programming formulations are presented and different properties of the problem are discussed. Several heuristic methods are presented and tested. Some of these procedures produce very close to optimal solutions very efficiently. In some cases, the computational times required to obtain these solutions are less than 1% of the computational time required for the conventional branch and bound algorithm. Several small examples are offered and the computational results of solving the problem for an actual, 181-bus transit property are reported.     

Scheduling considerations for a branching transit route

This paper addresses the impacts of different scheduling alternatives for a branching transit route. It examines different schedule alternatives that might be used to optimize the route performance in terms of the passenger traveling time distributed among branch passengers and trunk‐line passengers. The schedule alternatives considered include transit vehicle allocation to different branches, offset shifting across vehicles on different branches, and vehicle holding (slack time) in the transit vehicle schedule. With these variables, several vehicle schedules are devised and examined based on a wide variety of possible passenger boarding scenarios using deterministic service models. Test outcomes provide general conclusions about the performance of the strategies. Vehicle assignment leading to even headways among branches is generally preferred for the case of low passenger demand. However, when passenger demand is high, or the differences between the passenger demands on branches are significant, unequal vehicle assignment will be helpful to improve the overall route performance. Holding, as a proactive strategy in scheduling, has the potential to be embedded into the schedule as a type of slack time, but needs further evidence and study to determine the full set of conditions where it may be beneficial. Offset shifting does not show sufficient evidence to be an efficient strategy to improve route performance in the case of low or high passenger demand.     

A case study of Beijing bus crew scheduling: a variable neighborhood‐based approach

Crew scheduling for bus drivers in large bus agencies is known to be a time‐consuming and cumbersome problem in transit operations planning. This paper investigates a new meta‐heuristics approach for solving real‐world bus‐driver scheduling problems. The drivers' work is represented as a series of successive pieces of work with time windows, and a variable neighborhood search (VNS) algorithm is employed to solve the problem of driver scheduling. Examination of the modeling procedure developed is performed by a case study of two depots of the Beijing Public Transport Group, one of the largest transit companies in the world. The results show that a VNS‐based algorithm can reduce total driver costs by up to 18.1%, implying that the VNS algorithm may be regarded as a good optimization technique to solve the bus‐driver scheduling problem. Copyright © 2015 John Wiley & Sons, Ltd.     

Globally energy-optimal speed planning for road vehicles on a given route

This paper provides a globally optimal solution to an important problem: given a real-world route, what is the most energy-efficient way to drive a vehicle from the origin to the destination within a certain period of time. Along the route, there may be multiple stop signs, traffic lights, turns and curved segments, roads with different grades and speed limits, and even leading vehicles with pre-known speed profiles. Most of such route information and features are actually constraints to the optimal vehicle speed control problem, but these constraints are described in two different domains. The most important concept in solving this problem is to convert the distance-domain route constraints to some time-domain state and input constraints that can be handled by optimization methods such as dynamic programming (DP). Multiple techniques including cost-to-go function interpolation and parallel computing are used to reduce the computation of DP and make the problem solvable within a reasonable amount of time on a personal computer.     

Integrating a heterogeneous fixed fleet and a flexible assignment of destination depots in the waste collection VRP with intermediate facilities

We consider a complex recyclable waste collection problem that extends the class of vehicle routing problems with intermediate facilities by integrating a heterogeneous fixed fleet and a flexible assignment of destination depots. Several additional side constraints, such as a mandated break period contingent on tour start time, multiple vehicle capacities, and site dependencies are also included. This specific problem was inspired by a real-world application and does not appear in the literature. It is modeled as an MILP which is enhanced with several valid inequalities. Due to the rich nature of the problem, state-of-the-art solvers are only able to tackle instances of small to medium size. To solve realistic instances, we propose a multiple neighborhood search heuristic capable of systematically treating all problem features and general enough to respond to the varying characteristics of the case study regions for which it is intended. The results show that the heuristic achieves optimality on small instances, exhibits competitive performance in comparison to state-of-the-art solution methods for special cases of our problem, and leads to important savings in the state of practice. Moreover, it highlights and quantifies the savings from allowing a flexible depot assignment. The data from the state of practice comes from a company in the waste collection industry in Geneva, Switzerland.     

A differential evolution approach for the vehicle routing problem with backhauls and time windows

This paper presents a differential evolution algorithm (DEA) to solve a vehicle routing problem with backhauls and time windows (VRPBTW) and applied for a catering firm. VRPBTW is an extension of the vehicle routing problem, which includes capacity and time window constraints. In this problem, customers are divided into two subsets: linehaul and backhaul. Each vehicle starts from a depot and goods are delivered from the depot to the linehaul customers. Goods are subsequently brought back to the depot from the backhaul customers. The objective is to minimize the total distance that satisfies all of the constraints. The problem is formulated using mixed integer programming and solved using DEA. Proposed algorithm is tested with several benchmark problems to demonstrate effectiveness and efficiency of the algorithm and results show that our proposed algorithm can find superior solutions for most of the problems in comparison with the best known solutions. Hence, DEA was carried out for catering firm to minimize total transportation costs. Copyright © 2013 John Wiley & Sons, Ltd.     

Determining optimal frequency and vehicle capacity for public transit routes: A generalized newsvendor model

The level of service on public transit routes is very much affected by the frequency and vehicle capacity. The combined values of these variables contribute to the costs associated with route operations as well as the costs associated with passenger comfort, such as waiting and overcrowding. The new approach to the problem that we introduce combines both passenger and operator costs within a generalized newsvendor model. From the passenger perspective, waiting and overcrowding costs are used; from the operator’s perspective, the costs are related to vehicle size, empty seats, and lost sales. Maximal passenger average waiting time as well as maximal vehicle capacity are considered as constraints that are imposed by the regulator to assure a minimal public transit service level or in order to comply with other regulatory considerations. The advantages of the newsvendor model are that (a) costs are treated as shortages (overcrowding) and surpluses (empty seats); (b) the model presents simultaneous optimal results for both frequency and vehicle size; (c) an efficient and fast algorithm is developed; and (d) the model assumes stochastic demand, and is not restricted to a specific distribution. We demonstrate the usefulness of the model through a case study and sensitivity analysis.     

A subway planning bi-objective multi-period optimization model integrating timetabling and vehicle scheduling: a case study of Tehran

Due to the interaction among different planning levels and various travel demands during a day, the transit network planning is of great importance. In this paper, a bi-objective multi-period planning model is proposed for the synchronization of timetabling and vehicle scheduling. The main aim of the problem is to minimize the weighted transfer waiting time in the interchange stations along with the operational costs of vehicles. In order to demonstrate the effectiveness of the proposed integrated model, a real case study of Tehran subway is considered. The proposed model is solved by the ε-constraint method and some outstanding results are achieved.

     

Integrated scheduling of m-truck,m-drone,and m-depot constrained by time-window,drop-pickup,and m-visit using constraint programming

The idea of deploying unmanned aerial vehicles, also known as drones, for final-mile delivery in logistics operations has vitalized this new research stream. One conceivable scenario of using a drone in conjunction with a traditional delivery truck to distribute parcels is discussed in earlier literature and termed the parallel drone scheduling traveling salesman problem (PDSTSP). This study extends the problem by considering two different types of drone tasks: drop and pickup. After a drone completes a drop, the drone can either fly back to depot to deliver the next parcels or fly directly to another customer for pickup. Integrated scheduling of multiple depots hosting a fleet of trucks and a fleet of drones is further studied to achieve an operational excellence. A vehicle that travels near the boundary of the coverage area might be more effective to serve customers that belong to the neighboring depot. This problem is uniquely modeled as an unrelated parallel machine scheduling with sequence dependent setup, precedence-relationship, and reentrant, which gives us a framework to effectively consider those operational challenges. A constraint programming approach is proposed and tested with problem instances of m-truck, m-drone, m-depot, and hundred-customer distributed across an 8-mile square region.     

Intermodal Transit System Coordination

In urban areas where transit demand is widely spread, passengers may be served by an intermodal transit system, consisting of a rail transit line (or a bus rapid transit route) and a number of feeder routes connecting at different transfer stations. In such a system, passengers may need one or more transfers to complete their journey. Therefore, scheduling vehicles operating in the system with special attention to reduce transfer time can contribute significantly to service quality improvements. Schedule synchronization may significantly reduce transfer delays at transfer stations where various routes interconnect. Since vehicle arrivals are stochastic, slack time allowances in vehicle schedules may be desirable to reduce the probability of missed connections. An objective total cost function, including supplier and user costs, is formulated for optimizing the coordination of a general intermodal transit network. A four-stage procedure is developed for determining the optimal coordination status among routes at every transfer station. Considering stochastic feeder vehicle arrivals at transfer stations, the slack times of coordinated routes are optimized, by balancing the savings from transfer delays and additional cost from slack delays and operating costs. The model thus developed is used to optimize the coordination of an intermodal transit network, while the impact of a range of factors on coordination (e.g., demand, standard deviation of vehicle arrival times, etc) is examined.     

International experience with speed limits during and prior to the energy crisis of 1973–4

This paper presents an artificial neural network (ANN) based method for estimating route travel times between individual locations in an urban traffic network. Fast and accurate estimation of route travel times is required by the vehicle routing and scheduling process involved in many fleet vehicle operation systems such as dial‐a‐ride paratransit, school bus, and private delivery services. The methodology developed in this paper assumes that route travel times are time‐dependent and stochastic and their means and standard deviations need to be estimated. Three feed‐forward neural networks are developed to model the travel time behaviour during different time periods of the day‐the AM peak, the PM peak, and the off‐peak. These models are subsequently trained and tested using data simulated on the road network for the City of Edmonton, Alberta. A comparison of the ANN model with a traditional distance‐based model and a shortest path algorithm is then presented. The practical implication of the ANN method is subsequently demonstrated within a dial‐a‐ride paratransit vehicle routing and scheduling problem. The computational results show that the ANN‐based route travel time estimation model is appropriate, with respect to accuracy and speed, for use in real applications.     

Route design for last-in,first-out deliveries with backhauling

The retail route design problem extends the capacitated vehicle routing problem with time windows by introducing several operational constraints, including order loading and delivery restrictions (last-in, first-out), order-dependent vehicle capacity, material handling limits at the warehouse, backhauling, and driving time bounds. In this paper, the problem is modeled on a directed network for an application associated with a major grocery chain. Because the corresponding mixed-integer program proved too difficult to solve with commercial software for real instances, we developed a greedy randomized adaptive search procedure (GRASP) augmented with tabu search to provide solutions. Testing was done using data sets provided Kroger, the largest grocery chain in the US, and benchmarked against a previously developed column generation algorithm. The results showed that cost reductions of $4887 per day or 5.58% per day on average, compared to Kroger’s corresponding solutions.     

Efficient Transit Schedule Design of timing points: A comparison of Ant Colony and Genetic Algorithms

This work defines Transit Schedule Design (TSD) as an optimization problem to construct the transit schedule with the decision variables of the location of timing points and the amount of slack time associated with each timing point. Two heuristic procedures, Ant Colony and Genetic Algorithms, are developed for constructing optimal schedules for a fixed bus route. The paper presents a comparison of the fundamental features of the two algorithms. They are then calibrated based on data generated from micro-simulation of a bus route in Melbourne, Australia, to give rise to (near) optimal schedule designs. The algorithms are compared in terms of their accuracy and efficiency in providing the minimum cost solution. Although both procedures prove the ability to find the optimal solution, the Ant Colony procedure demonstrates a higher efficiency by evaluating less schedule designs to arrive at a ‘good’ solution. Potential benefits of the developed algorithms in bus route planning are also discussed.     

Flexible feeder transit route design to enhance service accessibility in urban area

To improve the accessibility of transit system in urban areas, this paper presents a flexible feeder transit routing model that can serve irregular‐shaped networks. By integrating the cost efficiency of fixed‐route transit system and the flexibility of demand responsive transit system, the proposed model is capable of letting operating feeder busses temporarily deviate from their current route so as to serve the reported demand locations. With an objective of minimizing total bus travel time, a new operational mode is then proposed to allow busses to serve passengers on both street sides. In addition, when multiple feeder busses are operating in the target service area, the proposed model can provide an optimal plan to locate the nearest one to response to the demands. A three‐stage solution algorithm is also developed to yield meta‐optimal solutions to the problem in a reasonable amount of time by transforming the problem into a traveling salesman problem. Numerical studies have demonstrated the effectiveness of the proposed model as well as the heuristic solution approach. Copyright © 2015 John Wiley & Sons, Ltd.     

Vehicle scheduling under stochastic trip times: An approximate dynamic programming approach

Due to unexpected demand surge and supply disruptions, road traffic conditions could exhibit substantial uncertainty, which often makes bus travelers encounter start delays of service trips and substantially degrades the performance of an urban transit system. Meanwhile, rapid advances of information and communication technologies have presented tremendous opportunities for intelligently scheduling a bus fleet. With the full consideration of delay propagation effects, this paper is devoted to formulating the stochastic dynamic vehicle scheduling problem, which dynamically schedules an urban bus fleet to tackle the trip time stochasticity, reduce the delay and minimize the total costs of a transit system. To address the challenge of “curse of dimensionality”, we adopt an approximate dynamic programming approach (ADP) where the value function is approximated through a three-layer feed-forward neural network so that we are capable of stepping forward to make decisions and solving the Bellman’s equation through sequentially solving multiple mixed integer linear programs. Numerical examples based on the realistic operations dataset of bus lines in Beijing have demonstrated that the proposed neural-network-based ADP approach not only exhibits a good learning behavior but also significantly outperforms both myopic and static polices, especially when trip time stochasticity is high.     

Routing and fleet deployment in liner shipping with spot voyages

The routing, scheduling and fleet deployment is an important integrated planning problem faced by liner shipping companies which also lift load from the spot market. This paper is concerned with coordinating the decisions of the assignment of ships to contractual and spot voyages, and the determination of ship routes and schedules in order to maximize profit. We propose a new model for representing voyages as nodes of a directed graph which is used to build a mixed integer programming formulation. Besides contractual and spot nodes, another type of node is put forward to represent a combination of a contractual voyage with one or more spot voyages. In addition, the concept of dominated nodes is introduced in order to discard them and reduce the effort of the search for an optimal solution. A set of test problems has been generated taking into account real world assumptions. The test problems are solved by an optimization software and computational results are reported. The results show the potential of the approach to solve test problems of moderate size.     

Transit network design by genetic algorithm with elitism

The transit network design problem is concerned with the finding of a set of routes with corresponding schedules for a public transport system. This problem belongs to the class of NP-Hard problem because of the vast search space and multiple constraints whose optimal solution is really difficult to find out. The paper develops a Population based model for the transit network design problem. While designing the transit network, we give preference to maximize the number of satisfied passengers, to minimize the total number of transfers, and to minimize the total travel time of all served passengers. Our approach to the transit network design problem is based on the Genetic Algorithm (GA) optimization. The Genetic Algorithm is similar to evolution strategy which iterates through fitness assessment, selection and breeding, and population reassembly. In this paper, we will show two different experimental results performed on known benchmark problems. We clearly show that results obtained by Genetic Algorithm with increasing population is better than so far best technique which is really difficult for future researchers to beat.     

Effective aircraft maintenance schedule adjustment following incidents

In the real world, planned aircraft maintenance schedules are often affected by incidents. Airlines may thus need to adjust their aircraft maintenance schedules following the incidents that occur during routine operations. In tradition, such aircraft maintenance schedule adjustment has been performed manually, a process which is neither effective nor efficient, especially when the problem scale is large. In this study, an aircraft maintenance schedule adjustment model is developed, with the objective of minimizing the total system cost, subject to the related operating constraints. The model is formulated as a zero-one integer program and is solved using a mathematical programing solver. The effectiveness of the model is evaluated by application to a case study using data from an aircraft maintenance center in Taiwan. The test results show the proposed model, as well as the scheduling rules abstracted from the results are useful for the decision maker to adjust good maintenance schedules.     

Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots

Dial-a-ride problems are concerned with the design of efficient vehicle routes for transporting individual persons from specific origin to specific destination locations. In real-life this operational planning problem is often complicated by several factors. Users may have special requirements (e.g. to be transported in a wheelchair) while service providers operate a heterogeneous fleet of vehicles from multiple depots in their service area. In this paper, a general dial-a-ride problem in which these three real-life aspects may simultaneously be taken into account is introduced: the Multi-Depot Heterogeneous Dial-A-Ride Problem (MD-H-DARP). Both a three- and two-index formulation are discussed. A branch-and-cut algorithm for the standard dial-a-ride problem is adapted to exactly solve small problem instances of the MD-H-DARP. To be able to solve larger problem instances, a new deterministic annealing meta-heuristic is proposed. Extensive numerical experiments are presented on different sets of benchmark instances for the homogeneous and the heterogeneous single depot dial-a-ride problem. Instances for the MD-H-DARP are introduced as well. The branch-and-cut algorithm provides considerably better results than an existing algorithm which uses a less compact formulation. All seven previously unsolved benchmark instances for the heterogeneous dial-a-ride problem could be solved to optimality within a matter of seconds. While computation times of the exact algorithm increase drastically with problem size, the proposed meta-heuristic algorithm provides near-optimal solutions within limited computation time for all instances. Several best known solutions for unsolved instances are improved and the algorithm clearly outperforms current state-of-the-art heuristics for the homogeneous and heterogeneous dial-a-ride problem, both in terms of solution quality and computation time.     

A column generation algorithm for the bus driver scheduling problem

Bus driver scheduling aims to find the minimum number of bus drivers to cover a published timetable of a bus company. When scheduling bus drivers, contractual working rules must be enforced, thus complicating the problem. In this research, we develop a column generation algorithm that decomposes this complicated problem into a master problem and a series of pricing subproblems. The master problem selects optimal duties from a set of known feasible duties, and the pricing subproblem augments the feasible duty set to improve the solution obtained in the master problem. The proposed algorithm is empirically applied to the realistic problems of several bus companies. The numerical results show that the proposed column generation algorithm can solve real‐world problems and obtain bus driver schedules that are better than those developed and used by the bus companies. Copyright © 2016 John Wiley & Sons, Ltd.