Heuristic approaches for flight retiming in an integrated airline scheduling problem of a regional carrier

Flight retiming in airline scheduling consists in slightly modifying the scheduled departure time of some flights with the goal of providing a better service with a cheaper cost. In this research, the departure times must be selected from a small discrete set of options. The whole problem embeds flight retiming, fleet assignment, aircraft routing and crew pairing. Thus, the aim is to determine the departure times of the flights, the fleet assignment and the minimum cost aircraft and crew routes. The objective function takes into account a large cost associated with each crew member, a penalization for short or long connection times, a cost for crew members changing aircraft along their routes, and a minor penalty associated with the use of each aircraft. The constraints enforce aircraft maintenance and crew working rules. In this setting, flight retiming is allowed to potentially reduce the total costs and increase the robustness of the solution against delays by decreasing the number of aircraft changes.We propose and compare four heuristic algorithms based on a Mixed Integer Linear Programming model for the whole problem. The model contains path variables representing the crew pairings, and arc variables representing the aircraft routes. In the heuristic algorithms, column generation is applied on the path variables, and different flight retiming options are considered. The algorithms are tested on real-world instances of a regional carrier flying in the Canary Islands to evaluate their advantages and drawbacks. In particular, one of the algorithms, that uses the solution of the Linear Programming relaxation of the model to select promising options for the departure of the flights, turns out to be the most effective one. The obtained results show that costs can be significantly reduced through flight retiming while still keeping the computing times reasonably short. In addition, we perform a sensitivity analysis by including more retiming options and by using different aircraft and crew costs. Finally, we report the results on larger size instances obtained by combining real-world ones.     

A continuous-time supply-driven inventory-constrained routing problem

We address an inventory routing problem (IRP) in which routing and inventory decisions are dictated by supply rather than demand. Moreover, inventory is held in containers that act as both a storage container and a movable transport unit. This problem emanates from logistics related to biogas transportation in which biogas is transported in containers from many suppliers to a single facility. We present a novel and compact formulation for the supply-driven IRP which addresses the routing decisions in continuous-time in which inventory levels within the containers are continuous. Valid inequalities are included and realistic instances are solved to optimality. For all experiments, we found that the total transportation time is minimized when the storage capacity at each supplier is larger than or equal to the vehicle capacity. These routes are characterized by tours in which mostly single suppliers are visited. In 95% of the instances, the average content level of the exchanged containers exceeded 99.6%.     

Logic-based Benders decomposition for an inventory-location problem with service constraints

We study an integrated inventory-location problem with service requirements faced by an aerospace company in designing its service parts logistics network. Customer demand is Poisson distributed and the service levels are time-based leading to highly non-linear, stochastic service constraints and a nonlinear, mixed-integer optimization problem. Unlike previous work in the literature, which propose approximations for the nonlinear constraints, we present an exact solution methodology using logic-based Benders decomposition. We decompose the problem to separate the location decisions in the master problem from the inventory decisions in the subproblem. We propose a new family of valid cuts and prove that the algorithm is guaranteed to converge to optimality. This is the first attempt to solve this type of problem exactly. Then, we present a new restrict-and-decompose scheme to further decompose the Benders master problem by part. We test on industry instances as well as random instances. Using the exact algorithm and restrict-and-decompose scheme we are able to solve industry instances with up to 60 parts within reasonable time, while the maximum number of parts attempted in the literature is 5.     

考虑延误因素的机组排班模型研究

机组排班是航空公司运营计划的重要环节。传统对机组排班问题的研究,通常不考虑延误对排班的影响,导致机组排班的鲁棒性较差。本文在传统机组排班模型的基础上考虑延误成本,以最小化各项任务成本和延误成本为目标,提出了考虑随机延误因素的机组排班数学规划模型。然后提出求解此模型的启发式列生成算法,该算法可有效缩小问题规模,减少求解过程中的迭代次数并提高求解质量。利用航空公司真实飞行数据进行测试,证明算法可在短时间内求解大规模机组排班问题。最后,通过仿真试验证实考虑延误的机组排班模型可有效提升排班的鲁棒性。     

Data aggregation for <Emphasis Type="Italic">p</Emphasis>-median problems

In this paper, we use a pseudo-Boolean formulation of the p-median problem and using data aggregation, provide a compact representation of p-median problem instances. We provide computational results to demonstrate this compactification in benchmark instances. We then use our representation to explain why some p-median problem instances are more difficult to solve to optimality than other instances of the same size. We also derive a preprocessing rule based on our formulation, and describe equivalent p-median problem instances, which are identical sized instances which are guaranteed to have identical optimal solutions.     

Revised GRASP with path-relinking for the linear ordering problem

The linear ordering problem (LOP) is an NP\mathcal{NP}-hard combinatorial optimization problem with a wide range of applications in economics, archaeology, the social sciences, scheduling, and biology. It has, however, drawn little attention compared to other closely related problems such as the quadratic assignment problem and the traveling salesman problem. Due to its computational complexity, it is essential in practice to develop solution approaches to rapidly search for solution of high-quality. In this paper we propose a new algorithm based on a greedy randomized adaptive search procedure (GRASP) to efficiently solve the LOP. The algorithm is integrated with a Path-Relinking (PR) procedure and a new local search scheme. We tested our implementation on the set of 49 real-world instances of input-output tables (LOLIB instances) proposed in Reinelt (Linear ordering library (LOLIB) 2002). In addition, we tested a set of 30 large randomly-generated instances proposed in Mitchell (Computational experience with an interior point cutting plane algorithm, Tech. rep., Mathematical Sciences, Rensellaer Polytechnic Institute, Troy, NY 12180-3590, USA 1997). Most of the LOLIB instances were solved to optimality within 0.87 seconds on average. The average gap for the randomly-generated instances was 0.0173% with an average running time of 21.98 seconds. The results indicate the efficiency and high-quality of the proposed heuristic procedure.     

Exact approaches for the pickup and delivery problem with loading cost

In this paper, we propose a branch-and-cut algorithm and a branch-and-price algorithm to solve the pickup and delivery problem with loading cost (PDPLC), which is a new problem derived from the classic pickup and delivery problem (PDP) by considering the loading cost in the objective function. Applications of the PDPLC arise in healthcare transportation where the objective function is customer-centric or service-based. In the branch-and-price algorithm, we devise an ad hoc label-setting algorithm to solve the pricing problem and employ the bounded bidirectional search strategy to accelerate the label-setting algorithm. The proposed algorithms were tested on a set of instances generated by a common data generator in the literature. The computational results showed that the branch-and-price algorithm outperformed the branch-and-cut algorithm by a large margin, and can solve instances with 40 requests to optimality in a reasonable time frame.     

Approaches to solve the fleet-assignment,aircraft-routing,crew-pairing and crew-rostering problems of a regional carrier

This paper presents the results of a research project funded by a regional carrier operating inter-island services within the Canary Islands (Spain) in addition to services to Morocco and Portugal. It operates between 100 and 150 flights a day using three airline operators. The main scope of the project was to solve fleet-assignment, aircraft-routing, crew-pairing and crew-rostering problems on real-world data. The special characteristics of the carrier, flying between 7 am and 11 pm every day, have motivated us to design models and algorithms that are different than the ones addressed in the literature, typically built for large airline companies. This paper shows a solution approach for an integrated fleet-assignment, aircraft-routing and crew-pairing problem covering the flights of a single day. This is a new combinatorial problem that can be considered as a 2-depot vehicle routing problem with driver changes, where the vehicles represent aircrafts and the drivers represent crews. Adapting approaches from the vehicle routing literature, this paper describes a heuristic algorithm based on an integer programming model. In a similar way, this paper also addresses the rostering problem. This problem can be decomposed in smaller problems taking into account operators, bases and crew groups. These problems admit a compact formulation through mixed integer linear programming models which can be tracked by modern general-purpose solvers. This paper illustrates the success of our solution approaches on real-world instances. The airline carrier is currently using these approaches.     

An exact semidefinite programming approach for the max-mean dispersion problem

This paper proposes an exact algorithm for the Max-Mean dispersion problem (\(Max-Mean DP\)), an NP-Hard combinatorial optimization problem whose aim is to select the subset of a set such that the average distance between elements is maximized. The problem admits a natural non-convex quadratic fractional formulation from which a semidefinite programming (SDP) relaxation can be derived. This relaxation can be tightened by means of a cutting plane algorithm which iteratively adds the most violated triangular inequalities. The proposed approach embeds the SDP relaxation and the cutting plane algorithm into a branch and bound framework to solve \(Max-Mean DP\) instances to optimality. Computational experiments show that the proposed method is able to solve to optimality in reasonable time instances with up to 100 elements, outperforming other alternative approaches.     

A Multi-Exchange Neighborhood for Minimum Makespan Parallel Machine Scheduling Problems

We propose new local search algorithms for minimum makespan parallel machine scheduling problems, which perform multiple exchanges of jobs among machines. Inspired by the work of Thompson and Orlin (1989) on cyclic transfer neighborhood structures, we model multiple exchanges of jobs as special disjoint cycles and paths in a suitably defined improvement graph, by extending definitions and properties introduced in the context of vehicle routing problems (Thompson and Psaraftis, 1993) and of the capacitated minimum spanning tree problem (Ahuja et al., 2001). Several algorithms for searching the neighborhood are suggested.We report the results of a wide computational experimentation, on different families of benchmark instances, performed for the case of identical machines. This problem has been selected as a case study to perform a comparison among the alternative algorithms, and to discover families of instances for which the proposed neighborhood may be promising in practice. Based on the results of the experiments, we can suggest which among the many possible variants of the proposed approaches may be more promising for developing local search algorithms based on multi-exchange moves for related problems. Also, on some families of instances, which are very hard to solve exactly, the most promising multi-exchange algorithms were observed to dominate, in solution quality and in computational time, competitive benchmark heuristics.     

Pareto mimic algorithm: An approach to the team orienteering problem

The team orienteering problem is an important variant of the vehicle routing problem. In this paper, a new algorithm, called Pareto mimic algorithm, is proposed to deal with it. This algorithm maintains a population of incumbent solutions which are updated using Pareto dominance. It uses a new operator, called mimic operator, to generate a new solution by imitating an incumbent solution. Furthermore, to improve the quality of a solution, it employs an operator, called swallow operator which attempts to swallow (or insert) an infeasible node and then repair the resulting infeasible solution. A comparative study supports the effectiveness of the proposed algorithm, especially, our algorithm can quickly find new better results for several large-scale instances. We also demonstrate that Pareto mimic algorithm can be generalized to solve other routing problems, e.g., the capacitated vehicle routing problem.     

Distribution with Quality of Service Considerations: The Capacitated Routing Problem with Profits and Service Level Requirements

Inspired by a problem arising in cash logistics, we propose the Capacitated Routing Problem with Profits and Service Level Requirements (CRPPSLR). The CRPPSLR extends the class of Routing Problems with Profits by considering customers requesting deliveries to their (possibly multiple) service points. Moreover, each customer imposes a service level requirement specifying a minimum-acceptable bound on the fraction of its service points being delivered. A customer-specific financial penalty is incurred by the logistics service provider when this requirement is not met. The CRPPSLR consists in finding vehicle routes maximizing the difference between the collected revenues and the incurred transportation and penalty costs in such a way that vehicle capacity and route duration constraints are met. A fleet of homogeneous vehicles is available for serving the customers. We design a branch-and-cut algorithm and evaluate the usefulness of valid inequalities that have been effectively used for the capacitated vehicle routing problem and, more recently, for other routing problems with profits. A real-life case study taken from the cash supply chain in the Netherlands highlights the relevance of the problem under consideration. Computational results illustrate the performance of the proposed solution approach under different input parameter settings for the synthetic instances. For instances of real-life problems, we distinguish between coin and banknote distribution, as vehicle capacities only matter when considering the former. Finally, we report on the effectiveness of the valid inequalities in closing the optimality gap at the root node for both the synthetic and the real-life instances and conclude with a sensitivity analysis on the most significant input parameters of our model.     

A multi-compartment vehicle routing problem arising in the collection of olive oil in Tunisia

We introduce, model and solve to optimality a rich multi-product, multi-period and multi-compartment vehicle routing problem with a required compartment cleaning activity. This real-life application arises in the olive oil collection process in Tunisia, where regional collection offices dispose of a fleet of vehicles to collect one or several grades of olive oil from a set of producers. For each grade, the quantity offered by a producer changes dynamically over the planning horizon. We first provide a mathematical formulation of the problem, along with a set of known and new valid inequalities. We then propose an exact branch-and-cut algorithm to solve the problem. We evaluate the performance of the algorithm on real data sets under different transportation scenarios to demonstrate to our industrial partner the advantages of using multi-compartment vehicles.     

Job-shop scheduling-joint consideration of production,transport, and storage/retrieval systems

This paper proposes a new problem by integrating the job shop scheduling, the part feeding, and the automated storage and retrieval problems. These three problems are intertwined and the performance of each of these problems influences and is influenced by the performance of the other problems. We consider a manufacturing environment composed of a set of machines (production system) connected by a transport system and a storage/retrieval system. Jobs are retrieved from storage and delivered to a load/unload area (LU) by the automated storage retrieval system. Then they are transported to and between the machines where their operations are processed on by the transport system. Once all operations of a job are processed, the job is taken back to the LU and then returned to the storage cell. We propose a mixed-integer linear programming (MILP) model that can be solved to optimality for small-sized instances. We also propose a hybrid simulated annealing (HSA) algorithm to find good quality solutions for larger instances. The HSA incorporates a late acceptance hill-climbing algorithm and a multistart strategy to promote both intensification and exploration while decreasing computational requirements. To compute the optimality gap of the HSA solutions, we derive a very fast lower bounding procedure. Computational experiments are conducted on two sets of instances that we also propose. The computational results show the effectiveness of the MILP on small-sized instances as well as the effectiveness, efficiency, and robustness of the HSA on medium and large-sized instances. Furthermore, the computational experiments clearly shown that importance of optimizing the three problems simultaneous. Finally, the importance and relevance of including the storage/retrieval activities are empirically demonstrated as ignoring them leads to wrong and misleading results.

     

Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem

In a previous work we proposed a variable fixing heuristics for the 0-1 Multidimensional knapsack problem (01MDK). This approach uses fractional optima calculated in hyperplanes which contain the binary optimum. This algorithm obtained best lower bounds on the OR-Library benchmarks. Although it is very attractive in terms of results, this method does not prove the optimality of the solutions found and may fix variables to a non-optimal value. In this paper, we propose an implicit enumeration based on a reduced costs analysis which tends to fix non-basic variables to their exact values. The combination of two specific constraint propagations based on reduced costs and an efficient enumeration framework enable us to fix variables on the one hand and to prune significantly the search tree on the other hand. Experimentally, our work provides two main contributions: (1) we obtain several new optimal solutions on hard instances of the OR-Library and (2) we reduce the bounds of the number of items at the optimum on several harder instances.     

动态需求下车辆路径问题的周期性优化模型及求解

针对客户点不断更新的动态需求车辆路径问题,依据滚动时域对配送中心工作时间进行划分,提出基于延迟服务的周期性客户点实时重置策略,策略中延迟服务机制能结合车辆启动延迟系数对照当前时域的时间进行检验,满足所有客户点的服务需求,保证车辆满足中心时间窗约束。设计多阶段求解的混合变邻域人工蜂群算法对各时间片内子问题进行连续迭代优化,算法中子路径动态转变的设计能较好平衡原有客户点和新客户点对路径更新和车辆实时信息匹配的要求。算例验证及对比分析表明本文策略和算法在求解动态问题时的有效性和可行性。     

Efficient Benders decomposition for distance-based critical node detection problem

This paper addresses the critical node detection problem which seeks a subset of nodes for removal in order to maximize the disconnectivity of the residual graph with respect to a specific distance-based measure, namely the Wiener index. Such a measure is defined based on the all-pair shortest path distances in the residual graph so that the longer the total length of shortest paths, the greater the value of the disconnectivity measure. In the literature, a mixed integer linear programming model and an exact iterative-based method have been presented for this problem; however, both approaches become very time-consuming on graphs having large diameter and non-unit edge lengths. To overcome this shortcoming, in this paper, we present a new formulation for the problem and solve it by Benders decomposition algorithm. We improve the performance of Benders algorithm by several techniques (including analytical calculation of dual variables, generation of good-quality initial optimality cuts, considering master's optimality cuts as lazy constraints, etc.) to reduce the total running time. The extensive computational experiments on instances, taken from the literature or generated randomly, confirm the effectiveness of the new approaches.     

考虑充电策略与电池损耗的电动汽车路径优化问题研究

针对目前研究电动物流车辆路径问题的文章未考虑电池损耗对运营成本的影响,且多在充电速率为恒定值的情况下对充电策略进行优化,本文将电动物流车辆在配送货物途中的充电时间和电池损耗成本纳入目标函数并建立了线性规划数学模型,统筹安排车辆行驶路径和充电策略使得物流企业整体运营成本最低。其次,提出了求解该问题的多阶段启发式算法MCWIGALNS。随后,通过多组算例验证了模型和算法的准确性。实验结果表明,考虑充电时间与深度放电成本的模型可以在配送距离不变或略有增加的情况下,较大幅度减少充电时间与电池损耗成本,到达降低运营成本的目的。最后,将算法实验结果与本领域已发表的成果进行比较,证明了MCWIGALNS算法对车辆路径问题具有出色的求解能力,提升了该问题理论成果的实用性。可以为物流企业电动汽车路径策略提供良好借鉴与帮助。     

Solving Steiner Tree Problems in Graphs with Lagrangian Relaxation

This paper presents an algorithm to obtain near optimal solutions for the Steiner tree problem in graphs. It is based on a Lagrangian relaxation of a multi-commodity flow formulation of the problem. An extension of the subgradient algorithm, the volume algorithm, has been used to obtain lower bounds and to estimate primal solutions. It was possible to solve several difficult instances from the literature to proven optimality without branching. Computational results are reported for problems drawn from the SteinLib library.     

Tabu search for the real-world carpooling problem

Carpooling is a flexible shared transportation system which can effectively reduce the vehicle numbers and fuel consumption. Although many carpooling systems have been proposed, most of them lack practicality, veracity, and efficiency. In this paper, we propose a new useful variant model of the long-term carpooling problem which involves multiple origins and one destination. Such problems commonly occur in a wide number of carpooling situations in real-world scenarios. Our work is motivated by the practical needs to solve environmental pollution, parking problems, traffic jams and low utilization of resources. A Tabu search algorithm is proposed in this paper to solve the carpooling problem. The proposed algorithm aims at a wide range of passenger distribution and routing problems. The computational results based on real world user data show the effectiveness of the proposed algorithm. Moreover, we developed a mobile application based on our carpooling model.