The split-demand one-commodity pickup-and-delivery travelling salesman problem

This paper introduces a new vehicle routing problem transferring one commodity between customers with a capacitated vehicle that can visit a customer more than once, although a maximum number of visits must be respected. It generalizes the capacitated vehicle routing problem with split demands and some other variants recently addressed in the literature. We model the problem with a single commodity flow formulation and design a branch-and-cut approach to solve it. We make use of Benders Decomposition to project out the flow variables from the formulation. Inequalities to strengthen the linear programming relaxation are also presented and separated within the approach. Extensive computational results illustrate the performance of the approach on benchmark instances from the literature.     

带时间窗的混和车辆路径问题的优化算法研究

文章针对带时间窗约束的混合车辆路径问题的特点,建立了带时间窗的混合车辆路径问题的数学模型,并设计了变邻域禁忌搜索算法对该问题进行求解。通过标准算例测试及与现有文献计算结果的比较,验证了该算法的有效性。     

A distributed VNS algorithm for optimizing dial-a-ride problems in large-scale scenarios

These days, transportation and logistic problems in large cities are demanding smarter transportation services that provide flexibility and adaptability. A possible solution to this arising problem is to compute the best routes for each new scenario. In this problem, known in the literature as the dial-a-ride problem, a number of passengers are transported between pickup and delivery locations trying to minimize the routing costs while respecting a set of prespecified constraints. This problem has been solved in the literature with several approaches from small to medium sized problems. However, few efforts have dealt with large scale problems very common in massive scenarios (big cities or highly-populated regions). In this study, a new distributed algorithm based on the partition of the requests space and the combination of the routes is presented and tested on a set of 24 different scenarios of a large-scale problem (up to 16,000 requests or 32,000 locations) in the city of San Francisco. The results show that, not only the distributed algorithm is able to solve large problem instances that the corresponding sequential algorithm is unable to solve in a reasonable time, but also to have an average improvement of 9% in the smaller problems. The results have been validated by means of statistical procedures proving that the distributed algorithm can be an effective way to solve high dimensional dial-a-ride problems.     

A multi-period dial-a-ride problem with driver consistency

Dial-a-ride services provide disabled and elderly people with a personalized mode of transportation to preserve their mobility. Typically, several users with different pickup and dropoff locations are transported on a vehicle simultaneously. The focus in dial-a-ride problems (DARPs) is mainly on minimizing routing cost. Service quality has been taken into account in the models by imposing time windows and limiting the maximum ride time of each user. We extend the classical DARP by an additional feature of service quality referred to as driver consistency. Customers of dial-a-ride services are often sensitive to changes in their daily routine. This aspect includes the person who is providing the transportation service, i.e., the driver of the vehicle. Our problem, called the driver consistent dial-a-ride problem (DC-DARP), considers driver consistency by bounding the maximum number of different drivers that transport a user over a multi-period planning horizon.We propose different formulations of the problem and examine their efficiency when applied in a Branch-and-Cut fashion. Additionally, we develop a large neighborhood search algorithm that generates near-optimal solutions in a short amount of time.Over 1000 instances are generated with close reference to real world scenarios. Extensive computational experiments are conducted in order to assess the quality of the solution approaches and to provide insights into the new problem. Results reveal that the cost of offering driver consistency varies greatly in magnitude. Depending on the instance, the cost of assigning one driver to each user can be up to 27.98% higher compared to a low-cost solution. However, routing cost increases by not more than 5.80% if users are transported by at least two drivers.     

Congestion-aware system optimal route choice for shared autonomous vehicles

We study the shared autonomous vehicle (SAV) routing problem while considering congestion. SAVs essentially provide a dial-a-ride service to travelers, but the large number of vehicles involved (tens of thousands of SAVs to replace personal vehicles) results in SAV routing causing significant congestion. We combine the dial-a-ride service constraints with the linear program for system optimal dynamic traffic assignment, resulting in a congestion-aware formulation of the SAV routing problem. Traffic flow is modeled through the link transmission model, an approximate solution to the kinematic wave theory of traffic flow. SAVs interact with travelers at origins and destinations. Due to the large number of vehicles involved, we use a continuous approximation of flow to formulate a linear program. Optimal solutions demonstrate that peak hour demand is likely to have greater waiting and in-vehicle travel times than off-peak demand due to congestion. SAV travel times were only slightly greater than system optimal personal vehicle route choice. In addition, solutions can determine the optimal fleet size to minimize congestion or maximize service.     

An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints

This study introduces a new practical variant of the combined routing and loading problem called the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints (3L-FCVRP). It presents a meta-heuristic algorithm for solving the problem. The aim is to design routes for a fleet of homogeneous vehicles that will serve all customers, whose demands are formed by a set of three-dimensional, rectangular, weighted items. Unlike the well-studied capacitated vehicle routing problem with 3D loading constraints (3L-CVRP), the objective of the 3L-FCVRP is to minimize total fuel consumption rather than travel distance. The fuel consumption rate is assumed to be proportionate to the total weight of the vehicle. A route is feasible only if a feasible loading plan to load the demanded items into the vehicle exists and the loading plan must satisfy a set of practical constraints.To solve this problem, the evolutionary local search (ELS) framework incorporating the recombination method is used to explore the solution space, and a new heuristic based on open space is used to examine the feasibility of the solutions. In addition, two special data structures, Trie and Fibonacci heap, are adopted to speed up the procedure. To verify the effectiveness of our approach, we first test the ELS on the 3L-CVRP, which can be seen as a special case of the 3L-FCVRP. The results demonstrate that on average ELS outperforms all of the existing approaches and improves the best-known solutions for most instances. Then, we generate data for 3L-FCVRP and report the detailed results of the ELS for future comparisons.     

Robust weekly aircraft maintenance routing problem and the extension to the tail assignment problem

In this paper, we study two closely related airline planning problems: the robust weekly aircraft maintenance routing problem (RWAMRP) and the tail assignment problem (TAP). In real life operations, the RWAMRP solution is used in tactical planning whereas the TAP solution is implemented in operational planning. The main objective of these two problems is to minimize the total expected propagated delay (EPD) of the aircraft routes. To formulate the RWAMRP, we propose a novel weekly line-of-flights (LOF) network model that can handle complex and nonlinear cost functions of EPD. Because the number of LOFs grows exponentially with the number of flights to be scheduled, we propose a two-stage column generation approach to efficiently solve large-scale real-life RWAMRPs. Because the EPD of an LOF is highly nonlinear and can be very time-consuming to accurately compute, we propose three lower bounds on the EPD to solve the pricing subproblem of the column generation. Our approach is tested on eight real-life test instances. The computational results show that the proposed approach provides very tight LP relaxation (within 0.6% of optimal solutions) and solves the test case with more than 6000 flights per week in less than three hours. We also investigate the solutions obtained by our approach over 500 simulated realizations. The simulation results demonstrate that, in all eight test instances, our solutions result in less EPDs than those obtained from traditional methods. We then extend our model and solution approach to solve realistically simulated TAP instances.     

A unified-adaptive large neighborhood search metaheuristic for periodic location-routing problems

This paper introduces three variants of the Periodic Location-Routing Problem (PLRP): the Heterogeneous PLRP with Time Windows (HPTW), the Heterogeneous PLRP (HP) and the homogeneous PLRP with Time Windows (PTW). These problems extend the well-known location-routing problem by considering a homogeneous or heterogeneous fleet, multiple periods and time windows. The paper develops a powerful Unified-Adaptive Large Neighborhood Search (U-ALNS) metaheuristic for these problems. The U-ALNS successfully uses existing algorithmic procedures and also offers a number of new advanced efficient procedures capable of handling a multi-period horizon, fleet composition and location decisions. Computational experiments on benchmark instances show that the U-ALNS is highly effective on PLRPs. The U-ALNS outperforms previous methods on a set of standard benchmark instances for the PLRP. We also present new benchmark results for the PLRP, HPTW, HP and PTW.     

The time-dependent vehicle routing problem with soft time windows and stochastic travel times

This paper studies a vehicle routing problem with time-dependent and stochastic travel times. In our problem setting, customers have soft time windows. A mathematical model is used in which both efficiency for service as well as reliability for customers are taken into account. Depending on whether service times are included or not, we consider two versions of this problem. Two metaheuristics are built: a Tabu Search and an Adaptive Large Neighborhood Search. We carry out our experiments for well-known problem instances and perform comprehensive analyses on the numerical results in terms of the computational time and the solution quality. Experiments confirm that the proposed procedure is effective to obtain very good solutions to be performed in real-life environment.     

A set-covering model for a bidirectional multi-shift full truckload vehicle routing problem

This paper introduces a bidirectional multi-shift full truckload transportation problem with operation dependent service times. The problem is different from the previous container transport problems and the existing approaches for container transport problems and vehicle routing pickup and delivery are either not suitable or inefficient. In this paper, a set covering model is developed for the problem based on a novel route representation and a container-flow mapping. It was demonstrated that the model can be applied to solve real-life, medium sized instances of the container transport problem at a large international port. A lower bound of the problem is also obtained by relaxing the time window constraints to the nearest shifts and transforming the problem into a service network design problem. Implications and managerial insights of the results by the lower bound results are also provided.     

Scheduling of airport runway operations using stochastic branch and bound methods

In this paper we present a solution methodology based on the stochastic branch and bound algorithm to find optimal, or close to optimal, solutions to the stochastic airport runway scheduling problem. The objective of the scheduling problem is to find a sequence of aircraft operations on one or several runways that minimizes the total makespan, given uncertain aircraft availability at the runway. Enhancements to the general stochastic branch and bound algorithm are proposed and we give the specific details pertaining to runway scheduling. We show how the algorithm can be terminated early with solutions that are close to optimal, and investigate the impact of the uncertainty level. The computational experiment indicates that the sequences obtained using the stochastic branch and bound algorithm have, on average, 5–7% shorter makespans than sequences obtained using deterministic sequencing models. In addition, the proposed algorithm is able to solve instances with 14 aircraft using less than 1 min of computation time.     

An optimization model for aircraft maintenance scheduling and re-assignment

The aircraft maintenance scheduling is one among the major decisions an airline has to make during its operation. Though maintenance scheduling comes as an end stage in an airline operation, it has potential for cost savings. Maintenance scheduling is an easily understood but difficult to solve problem. Given a flight schedule with aircraft assigned to it, the aircraft maintenance-scheduling problem is to determine which aircraft should fly which segment and when and where each aircraft should undergo different levels of maintenance check required by the Federal Aviation Administration. The objective is to minimize the maintenance cost and any costs incurred during the re-assignment of aircraft to the flight segments.This paper provides a complete formulation for maintenance scheduling and a heuristic approach to solve the problem. The heuristic procedure provides good solutions in reasonable computation time. This model can be used by mid-sized airline corporations to optimize their maintenance costs.     

The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity

This paper introduces a fleet size and mix dial-a-ride problem with multiple passenger types and a heterogeneous fleet of reconfigurable vehicles. In this new variant of the dial-a-ride problem, en-route modifications of the vehicle’s inner configuration are allowed. The main consequence is that the vehicle capacity is defined by a set of configurations and the choice of vehicle configuration is associated with binary decision variables.The problem is modeled as a mixed-integer program derived from the model of the heterogeneous dial-a-ride problem. Vehicle reconfiguration is a lever to efficiently reduce transportation costs, but the number of passengers and vehicle fleet setting make this problem intractable for exact solution methods. A large neighborhood search metaheuristic combined with a set covering component with a reactive mechanism to automatically adjust its parameters is therefore proposed. The resulting framework is evaluated against benchmarks from the literature, used for similar routing problems. It is also applied to a real case, in the context of the transportation of disabled children from their home to medical centers in the city of Lyon, France.     

The time-dependent pollution-routing problem

The Time-Dependent Pollution-Routing Problem (TDPRP) consists of routing a fleet of vehicles in order to serve a set of customers and determining the speeds on each leg of the routes. The cost function includes emissions and driver costs, taking into account traffic congestion which, at peak periods, significantly restricts vehicle speeds and increases emissions. We describe an integer linear programming formulation of the TDPRP and provide illustrative examples to motivate the problem and give insights about the tradeoffs it involves. We also provide an analytical characterization of the optimal solutions for a single-arc version of the problem, identifying conditions under which it is optimal to wait idly at certain locations in order to avoid congestion and to reduce the cost of emissions. Building on these analytical results we describe a novel departure time and speed optimization algorithm for the cases when the route is fixed. Finally, using benchmark instances, we present results on the computational performance of the proposed formulation and on the speed optimization procedure.     

Transportation service procurement problem with transit time

In this work, we investigate transit time in transportation service procurement, which is conducted by shippers using auctions to purchase transportation service from carriers in the planning stage. Besides cost, we find that many shippers are most concerned with transit time in practice; shorter transit time indicates better transportation service. To minimize both the total cost and transit time, the problem faced by shippers is the biobjective transportation service procurement problem with transit time. To solve the problem, we introduce a biobjective integer programming model that can also accommodate some important business constraints. A biobjective branch-and-bound algorithm that finds all extreme supported nondominated solutions is developed. To speed up the algorithm, two fast feasibility checks, a network flow model for particular subproblems, and lower bounds from relaxation are proposed. In addition, a sophisticated heuristic is introduced to meet shipper’s requirements in some situations. Computational experiments on evaluating the performance of the algorithms are conducted on a set of test instances that are generated from practical data.     

Optimization of periodic crew schedules with application of column generation method

We present an alternative approach to the problem of periodic crew scheduling. We introduce the concept of frames which leads us to a modeling approach which suits well the current practice of the majority of European railway operators. It results in a model facilitating column generation techniques resulting in a Dantzig-Wolfe type decomposition, and thus suitable for a parallel implementation in a high-performance computing environment. We exploit the properties of network flow models to avoid several additional integer constraints. We compare two approaches to solve the problem. The first approach consists of solving the original problem by single model. The second approach is our step-by-step column generation. The comparison is based on our implementation which we describe in detail along with its application to certain benchmark instances. The benchmarks originate in real or close-to-realistic problems from railway systems in Slovakia and Hungary. The case studies demonstrate that our model is well-suited for real-life applications.     

A math-heuristic algorithm for the integrated air service recovery

A sophisticated flight schedule might be easily disrupted due to adverse weather, aircraft mechanical failures, crew absences, etc. Airlines incur huge costs stemming from such flight schedule disruptions in addition to the serious inconveniences experienced by passengers. Therefore, an efficient recovery solution that simultaneously decreases an airline's recovery cost while simultaneously mitigating passenger dissatisfaction is of great importance to the airline industry. In this paper, we study the integrated airline service recovery problem in which the aircraft and passenger schedule recovery problems are simultaneously addressed, with the objective of minimizing aircraft recovery and operating costs, passenger itinerary delay cost, and passenger itinerary cancellation cost.Recognizing the inherent difficulty in modeling the integrated airline service recovery problem within a single formulation (due to its huge solution space and quick response requirement), we propose a three-stage sequential math-heuristic framework to efficiently solve this problem, wherein the flight schedules and aircraft rotations are recovered in the first stage, Then, a flight rescheduling problem and passenger schedule recovery problems are iteratively solved in the next two stages. Time-space network flow representations, along with mixed-integer programming formulations, and algorithms that take advantages of the underlying problem structures, are proposed for each of three stages. This algorithm was tested on realistic data provided by the ROADEF 2009 challenge and the computational results reveal that our algorithm generated the best solution in nearly 72% of the test instances, and a near-optimal solution was achieved in the remaining instances within an acceptable timeframe. Furthermore, we also ran additional computational runs to explore the underlying characteristics of the proposed algorithm, and the recorded insights can serve as a useful guide during practical implementations of this algorithm.     

Service type assignment and container routing with transit time constraints and empty container repositioning for liner shipping service networks

A decision tool is developed for a liner shipping company to deploy its fleet considering vessel speeds and to find routes for cargos with repositioning of empty containers and transit time constraints. This problem is referred as the simultaneous Service type Assignment and container Routing Problem (SARP) in the sequel. A path-flow based mixed-integer linear programming formulation is suggested for the SARP. A Branch and Bound (BB) algorithm is used to solve the SARP exactly. A Column Generation (CG) procedure, embedded within the BB framework, is devised to solve the linear programming relaxation of the SARP. The CG subproblems arises as Shortest Path Problems (SPP). Yet incorporating transit time requirements yields constrained SPP which is NP-hard and solved by a label correcting algorithm. Computational experiments are performed on randomly generated test instances mimicking real life. The BB algorithm yields promising solutions for the SARP. The SARP with and without transit time constraints is compared with each other. Our results suggest a potential to increase profit margins of liner shipping companies by considering transit time requirements of cargos.     

The fleet size and mix pollution-routing problem

This paper introduces the fleet size and mix pollution-routing problem which extends the pollution-routing problem by considering a heterogeneous vehicle fleet. The main objective is to minimize the sum of vehicle fixed costs and routing cost, where the latter can be defined with respect to the cost of fuel and CO₂ emissions, and driver cost. Solving this problem poses several methodological challenges. To this end, we have developed a powerful metaheuristic which was successfully applied to a large pool of realistic benchmark instances. Several analyses were conducted to shed light on the trade-offs between various performance indicators, including capacity utilization, fuel and emissions and costs pertaining to vehicle acquisition, fuel consumption and drivers. The analyses also quantify the benefits of using a heterogeneous fleet over a homogeneous one.     

Approximate algorithms for the discrete network design problem

The discrete network design problem is one of finding a set of feasible actions (projects) from among a collection of possible actions, that when implemented, optimizes some objective function(s). This is a combinatorial optimization problem that is very expensive to solve exactly. This paper proposes two algorithms for obtaining approximate solutions to the discrete network design problem with much less computational effeort. The computational savings are achieved by approximating the original problem with a new formulation which is easier to solve. The first algorithm proposed solves this approximate problem exactly, while the second is even more efficient, but provides only a near-optimal solution to the approximate problem. Experience with test problems indicates that these approximations can reduce the computational effort by a factor of 3–5, with little loss in solution accuracy.