A variable neighborhood search heuristic for periodic routing problems

The aim of this paper is to propose a new heuristic for the Periodic Vehicle Routing Problem (PVRP) without time windows. The PVRP extends the classical Vehicle Routing Problem (VRP) to a planning horizon of several days. Each customer requires a certain number of visits within this time horizon while there is some flexibility on the exact days of the visits. Hence, one has to choose the visit days for each customer and to solve a VRP for each day. Our method is based on Variable Neighborhood Search (VNS). Computational results are presented, that show that our approach is competitive and even outperforms existing solution procedures proposed in the literature. Also considered is the special case of a single vehicle, i.e. the Periodic Traveling Salesman Problem (PTSP). It is shown that slight changes of the proposed VNS procedure is also competitive for the PTSP.     

Optimizing the periodic pick-up of raw materials for a manufacturer of auto parts

We describe a solution procedure for a special case of the periodic vehicle routing problem (PVRP). Operation managers at an auto parts manufacturer in the north of Spain described the optimization problem to the authors. The manufacturer must pick up parts (raw material) from geographically dispersed locations. The parts are picked up periodically at scheduled times. The problem consists of assigning a pickup schedule to each of its supplier’s locations and also establishing daily routes in order to minimize total transportation costs. The time horizon under consideration may be as long as 90 days. The resulting PVRP is such that the critical decision is the assignment of locations to schedules, because once this is done, the daily routing of vehicles is relatively straightforward. Through extensive computational experiments, we show that the metaheuristic procedure described in this paper is capable of finding high-quality solutions within a reasonable amount of computer time. Our main contribution is the development of a procedure that is more effective at handling PVRP instances with long planning horizons when compared to those proposed in the literature.     

On a periodic vehicle routing problem

This paper deals with a study on a variant of the Periodic Vehicle Routing Problem (PVRP). As in the traditional Vehicle Routing Problem, customer locations each with a certain daily demand are given, as well as a set of capacitated vehicles. In addition, the PVRP has a horizon, say T days, and there is a frequency for each customer stating how often within this T-day period this customer must be visited. A solution to the PVRP consists of T sets of routes that jointly satisfy the demand constraints and the frequency constraints. The objective is to minimize the sum of the costs of all routes over the planning horizon. We develop different algorithms solving the instances of the case studied. Using these algorithms we are able to realize considerable cost reductions compared to the current situation.     

Operational aircraft maintenance routing problem with remaining time consideration

The aircraft maintenance routing problem is one of the most studied problems in the airline industry. Most of the studies focus on finding a unique rotation that will be repeated by each aircraft in the fleet with a certain lag. In practice, using a single rotation for the entire fleet is not applicable due to stochasticity and operational considerations in the airline industry. In this study, our aim is to develop a fast responsive methodology which provides maintenance feasible routes for each aircraft in the fleet over a weekly planning horizon with the objective of maximizing utilization of the total remaining flying time of fleet. For this purpose, we formulate an integer linear programming (ILP) model by modifying the connection network representation. The proposed model is solved by using branch-and-bound under different priority settings for variables to branch on. A heuristic method based on compressed annealing is applied to the same problem and a comparison of exact and heuristic methods are provided. The model and the heuristic method are extended to incorporate maintenance capacity constraints. Additionally, a rolling horizon based procedure is proposed to update the existing routes when some of the maintenance decisions are already fixed.     

Heuristic algorithms for a multi-period multi-stop transportation planning problem

We consider a multi-period multi-stop transportation planning problem (MPMSTP) in a one-warehouse multi-retailer distribution system where a fleet of homogeneous vehicles delivers products from a warehouse to retailers. The objective of the MPMSTP is to minimize the total transportation distance for product delivery over the planning horizon while satisfying demands of the retailers. We suggest two heuristic algorithms based on the column generation method and the simulated annealing algorithm. Computational experiments on randomly generated test problems showed that the suggested algorithms gave better solutions than an algorithm currently used in practice and algorithms modified from existing algorithms for vehicle routing problems.     

A heuristic for the multi-satellite,multi-orbit and multi-user management of Earth observation satellites

Earth observation satellites are platforms equipped with optical instruments that orbit the Earth in order to take photographs of specific areas at the request of users. This article is concerned with the management of several satellites performing multiple orbits over a given planning horizon. It describes a tabu search heuristic for the problem of selecting and scheduling the requests to be satisfied, under operational constraints. An upper bounding procedure based on column generation is used to evaluate the quality of the solutions. The results of extensive computational experiments performed on data provided by the French Centre National d’Études Spatiales are reported.     

A hybrid evolutionary algorithm for the periodic location-routing problem

The well-known vehicle routing problem (VRP) has been studied in depth over the last decades. Nowadays, generalizations of VRP have been developed for tactical or strategic decision levels of companies but not both. The tactical extension or periodic VRP (PVRP) plans a set of trips over a multiperiod horizon, subject to frequency constraints. The strategic extension is motivated by interdependent depot location and routing decisions in most distribution systems. Low-quality solutions are obtained if depots are located first, regardless of the future routes. In the location-routing problem (LRP), location and routing decisions are tackled simultaneously. Here for the first time, except for some conference papers, the goal is to combine the PVRP and LRP into an even more realistic problem covering all decision levels: the periodic LRP or PLRP. A hybrid evolutionary algorithm is proposed to solve large size instances of the PLRP. First, an individual representing an assignment of customers to combinations of visit days is randomly generated. The evolution operates through an Evolutionary Local Search (ELS) on visit day assignments. The algorithm is hybridized with a heuristic based on the Randomized Extended Clarke and Wright Algorithm (RECWA) to create feasible solutions and stops when a given number of iterations is reached. The method is evaluated over three sets of instances, and solutions are compared to the literature on particular cases such as one-day horizon (LRP) or one depot (PVRP). This metaheuristic outperforms the previous methods for the PLRP.     

考虑订单合并和货物转运的多式联运路径优化研究

为了获得运输的规模经济效应,本文研究了一种考虑订单合并和货物转运的零担多式联运路径优化问题。首先,以总运输成本为目标函数,以网络中的运输工具容量、可以提供的运输工具最大数量、运输工具服务的关闭时间以及订单时间窗为约束,构建混合整数规划模型,在模型中允许多个订单进行合并运输并考虑运输过程中的转运成本。其次,由于多式联运路径优化问题是典型的NP-hard问题,为了快速求解该模型,开发了一种可以快速为该问题提供近似最优解和下界的列生成启发式算法。最后,生成并测试了大量算例,结果表明所开发的列生成启发式算法可以在较短的时间内提供高质量的近似最优解。文章所构建的模型和开发的列生成启发式算法可以为零担自营多式联运物流企业提供高效的决策支持。     

Column generation for vehicle routing problems with multiple synchronization constraints

Synchronization of workers and vehicles plays a major role in many industries such as logistics, healthcare or airport ground handling. In this paper, we focus on operational ground handling planning and model it as an archetype of vehicle routing problems with multiple synchronization constraints, coined as “abstract vehicle routing problem with worker and vehicle synchronization” (AVRPWVS). The AVRPWVS deals with routing workers to ground handling jobs such as unloading baggage or refuelling an aircraft, while meeting each job’s time window. Moreover, each job can be performed by a variable number of workers. As airports span vast distances and due to security regulations, workers use vehicles to travel between locations. Furthermore, each vehicle, moved by a driver, can carry several workers. We propose two mathematical multi-commodity flow formulations based on time-space networks to efficiently model five synchronization types including movement and load synchronization. Moreover, we develop a branch-and-price heuristic that employs both conventional variable branching and a novel variable fixing strategy. We demonstrate that the procedure achieves results close to the optimal solution in short time when compared to the two integer models.     

改进蚁群算法优化周期性车辆路径问题

周期性车辆路径问题(PVRP)是标准车辆路径问题(VRP)的扩展,PVRP将配送期由单一配送期延伸到T(T＞1)期,因此,PVRP需要优化每个配送期的顾客组合和配送路径。由于PVRP是一个内嵌VRP的问题,其比标准VRP问题更加复杂,难于求解。本文采用蚁群算法对PVRP进行求解,并提出采用两种改进措施——多维信息素的运用和基于扫描法的局部优化方法来提高算法的性能。最后,通过9个经典PVRP算例对该算法进行了数据实验,结果表明本文提出的改进蚁群算法求解PVRP问题是可行有效的,同时也表明两种改进措施可以显著提高算法的性能。     

Decomposition methods for the lot-sizing and cutting-stock problems in paper industries

We investigate the one-dimensional cutting-stock problem integrated with the lot-sizing problem in the context of paper industries. The production process in paper mill industries consists of producing raw materials characterized by rolls of paper and cutting them into smaller rolls according to customer requirements. Typically, both problems are dealt with in sequence, but if the decisions concerning the cutting patterns and the production of rolls are made together, it can result in better resource management. We investigate Dantzig–Wolfe decompositions and develop column generation techniques to obtain upper and lower bounds for the integrated problem. First, we analyze the classical column generation method for the cutting-stock problem embedded in the integrated problem. Second, we propose the machine decomposition that is compared with the classical period decomposition for the lot-sizing problem. The machine decomposition model and the period decomposition model provide the same lower bound, which is recognized as being better than the linear relaxation of the classical lot-sizing model. To obtain feasible solutions, a rounding heuristic is applied after the column generation method. In addition, we propose a method that combines an adaptive large neighborhood search and column generation method, which is performed on the machine decomposition model. We carried out computational experiments on instances from the literature and on instances adapted from real-world data. The rounding heuristic applied to the first column generation method and the adaptive large neighborhood search combined with the column generation method are efficient and competitive.     

A column generation approach for an emission-oriented vehicle routing problem on a multigraph

In this work, an emission-minimizing vehicle routing problem with heterogeneous vehicles and a heterogeneous road and traffic network is considered as it is typical in urban areas. Depending on the load of the vehicle, there exist multiple emission-minimal arcs for traveling between two locations. To solve the vehicle routing problem efficiently, a column generation approach is presented. At the core of the procedure an emission-oriented elementary shortest path problem on a multigraph is solved by a backward labeling algorithm. It is shown that the labeling algorithm can be sped up by adjusting the dual master program and by restricting the number of labels propagated in the sub-problem. The column generation technique is used to setup a fast heuristic as well as a branch-and-price algorithm. Both procedures are evaluated based on test instances with up to 100 customers. It turns out that the heuristic approach is very effective and generates near-optimal solutions with gaps below 0.1% on average while only requiring a fraction of the runtime of the exact approach.     

A column generation heuristic for congested facility location problem with clearing functions

Nonlinear clearing functions, an idea initially suggested to reflect congestion effects in production planning, are used to express throughput of facilities prone to congestion in a facility location problem where each demand site is served by exactly one facility. The traditional constant capacity constraint for a facility is replaced with the nonlinear clearing function. The resulting nonlinear integer problem is solved by a column generation heuristic in which initial columns for the restricted master problem are generated by known existing algorithms and additional columns by a previously developed dynamic programming algorithm. Computational experimentation in terms of dual gap and CPU time based on both randomly generated and published data sets show not only clear dominance of the column generation over a Lagrangian heuristic previously developed, but also the high quality of results from the suggested heuristic for large problems.     

Simultaneous evacuation and entrance planning in complex building based on dynamic network flows

This paper presents mathematical models and a heuristic algorithm that address a simultaneous evacuation and entrance planning. For the simultaneous evacuation and entrance planning, four types of mathematical models based on the discrete time dynamic network flow model are developed to provide the optimal routes for evacuees and responders within a critical timeframe. The optimal routes obtained by the mathematical models can minimize the densification of evacuees and responders into specific areas. However, the mathematical model has a weakness in terms of long computation time for the large-size problem. To overcome the limitation, we developed a heuristic algorithm. We also analyzed the characteristics of each model and the heuristic algorithm by conducting case studies. This study pioneers area related to evacuation planning by developing and analyzing four types of mathematical models and a heuristic algorithm which take into account simultaneous evacuation and entrance planning.     

An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles

The vehicle routing problem with multiple use of vehicles is a variant of the classical vehicle routing problem. It arises when each vehicle performs several routes during the workday due to strict time limits on route duration (e.g., when perishable goods are transported). The routes are defined over customers with a revenue, a demand and a time window. Given a fixed-size fleet of vehicles, it might not be possible to serve all customers. Thus, the customers must be chosen based on their associated revenue minus the traveling cost to reach them. We introduce a branch-and-price approach to address this problem where lower bounds are computed by solving the linear programming relaxation of a set packing formulation, using column generation. The pricing subproblems are elementary shortest path problems with resource constraints. Computational results are reported on euclidean problems derived from well-known benchmark instances for the vehicle routing problem with time windows.     

考虑均衡性的不确定时间车辆调度问题研究

本文针对车辆调度实际运行过程中时间的不确定性问题,提出了包含时间窗口、车辆容量约束的配送服务线路随机规划模型,以最小化调用的车辆数目和运行距离,降低顾客的不满意度并且尽可能保证每条路线的均衡性。结合模型,给出了基于禁忌搜索的混合启发式算法,并且生成多个算例,依据算例结果说明模型和算法优越性,同时说明可以在不降低顾客满意度和不提高总运输成本的基础上,降低各条线路之间的时间差异。     

The periodic vehicle routing problem with intermediate facilities

In this paper, we study an extension of the PVRP where the vehicles can renew their capacity at some intermediate facilities. Each vehicle returns to the depot only when its work shift is over. For this problem we propose a tabu search (TS) algorithm and present computational results on a set of randomly generated instances and on a set of PVRP instances taken from the literature.     

Managing vehicle breakdown incidents during urban distribution of a common product

This paper addresses a case in which a vehicle, member of a fleet distributing a single product, is immobilized while executing its distribution plan. Some active vehicles of the fleet are then rerouted to serve selected clients of the immobilized vehicle. We model this re-planning problem as a variation of the Team Orienteering Problem constraining all vehicle routes to an upper time, or distance, limit, and taking into account limited vehicle capacity. We propose an efficient heuristic to provide solutions in almost real-time. The heuristic progressively constructs new routes for each active vehicle, which may load additional product by visiting the warehouse or the immobilized vehicle. If appropriate, we solve this replenishment sub-problem by a fast labelling algorithm. We test the effectiveness of the proposed heuristic by comparing its solutions with those obtained by an appropriate Genetic Algorithm (GA) that yields high quality (but computationally expensive) results.     

Airline crew scheduling from planning to operations

Crew scheduling problems at the planning level are typically solved in two steps: first, creating working patterns, and then assigning these to individual crew. The first step is solved with a set covering model, and the second with a set-partitioning model. At the operational level, the (re) planning period is considerably smaller than during the strategic planning phase. We integrate both models to solve time critical crew recovery problems arising on the day of operations. We describe how pairing construction and pairing assignment are done in a single step, and provide solution techniques based on simple tree search and more sophisticated column generation and shortest-path algorithms.     

Improved rounding procedures for the discrete version of the capacitated EOQ problem

We consider a transportation problem where different products have to be shipped from an origin to a destination by means of vehicles with given capacity. The production rate at the origin and the demand rate at the destination are constant over time and identical for each product. The problem consists in deciding when to make the shipments and how to fill the vehicles, with the objective of minimizing the sum of the average transportation and inventory costs at the origin and at the destination over an infinite horizon. This problem is the well known capacitated EOQ (economic order quantity) problem and has an optimal solution in closed form. In this paper we study a discrete version of this problem in which shipments are performed only at multiples of a given minimum time. It is known that rounding-off the optimal solution of the capacitated EOQ problem to the closest lower or upper integer value gives a tight worst-case ratio of 2, while the best among the possible single frequency policies has a performance ratio of 5/3. We show that the 5/3 bound can be obtained by a single frequency policy based on a rounding procedure which considers classes of instances and, for each class, identifies a shipping frequency by rounding-off in a different way the optimal solution of the capacitated EOQ problem. Moreover, we show that the bound can be reduced to 3/2 by using two shipping frequencies, obtained by a rounding procedure, in one class of instances only.