A branch-and-price algorithm to solve the molten iron allocation problem in iron and steel industry

The molten iron allocation problem (MIAP) is to allocate molten iron from blast furnaces to steel-making furnaces. The allocation needs to observe the release times of the molten iron defined by the draining plan of the blast furnaces and the transport time between the iron-making and steel-making stages. Time window constraints for processing the molten iron must be satisfied to avoid freezing. The objective is to find a schedule with minimum total weighted completion time. This objective reflects the practical consideration of improving steel-making efficiency and reducing operation cost caused by the need for reheating. Such a problem can be viewed as a parallel machine scheduling problem with time windows which is known to be NP-hard. In this paper, we first formulate the molten iron allocation problem as an integer programming model and then reformulate it as a set partitioning model by applying the Dantzig–Wolfe decomposition. We solve the problem using a column generation-based branch-and-price algorithm. Since the subproblem of column generation is still NP-hard, we propose a state-space relaxation-based dynamic programming algorithm for the subproblem. Computational experiments demonstrate that the proposed algorithm is capable of solving problems with up to 100 jobs to optimality within a reasonable computation time.     

A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows

Multi-objective evolutionary algorithm based on decomposition (MOEA/D) provides an excellent algorithmic framework for solving multi-objective optimization problems. It decomposes a target problem into a set of scalar sub-problems and optimizes them simultaneously. Due to its simplicity and outstanding performance, MOEA/D has been widely studied and applied. However, for solving the multi-objective vehicle routing problem with time windows (MO-VRPTW), MOEA/D faces a difficulty that many sub-problems have duplicated best solutions. It is well-known that MO-VRPTW is a challenging problem and has very few Pareto optimal solutions. To address this problem, a novel selection operator is designed in this work to enhance the original MOEA/D for dealing with MO-VRPTW. Moreover, three local search methods are introduced into the enhanced algorithm. Experimental results indicate that the proposed algorithm can obtain highly competitive results on Solomon׳s benchmark problems. Especially for instances with long time windows, the proposed algorithm can obtain more diverse set of non-dominated solutions than the other algorithms. The effectiveness of the proposed selection operator is also demonstrated by further analysis.     

Vehicle routing problem with a heterogeneous fleet and time windows

In this paper, a problem variant of the vehicle routing problem with time windows is introduced to consider vehicle routing with a heterogeneous fleet, a limited number of vehicles and time windows. A method that extends an existing tabu search procedure to solve the problem is then proposed. To evaluate the performance of the proposed method, experiments are conducted on a large set of test cases, which comprises several benchmark problems from numerous problem variants of the vehicle routing problem with a heterogeneous fleet. It is observed that the proposed method can be used to give reasonably good results for these problem variants. In addition, some ideas are presented to advance the research in heuristics, such as fair reporting standards, publication of benchmark problems and executable routines developed for algorithmic comparison.     

Waste collection vehicle routing problem with time windows

In this paper, we address a real life waste collection vehicle routing problem with time windows (VRPTW) with consideration of multiple disposal trips and drivers’ lunch breaks. Solomon's well-known insertion algorithm is extended for the problem. While minimizing the number of vehicles and total traveling time is the major objective of vehicle routing problems in the literature, here we also consider the route compactness and workload balancing of a solution since they are very important aspects in practical applications. In order to improve the route compactness and workload balancing, a capacitated clustering-based waste collection VRPTW algorithm is developed. The proposed algorithms have been successfully implemented and deployed for the real life waste collection problems at Waste Management, Inc. A set of waste collection VRPTW benchmark problems is also presented in this paper.Waste collection problems are frequently considered as arc routing problems without time windows. However, that point of view can be applied only to residential waste collection problems. In the waste collection industry, there are three major areas: commercial waste collection, residential waste collection and roll-on-roll-off. In this paper, we mainly focus on the commercial waste collection problem. The problem can be characterized as a variant of VRPTW since commercial waste collection stops may have time windows. The major variation from a standard VRPTW is due to disposal operations and driver's lunch break. When a vehicle is full, it needs to go to one of the disposal facilities (landfill or transfer station). Each vehicle can, and typically does, make multiple disposal trips per day. The purpose of this paper is to introduce the waste collection VRPTW, benchmark problem sets, and a solution approach for the problem. The proposed algorithms have been successfully implemented and deployed for the real life waste collection problems of Waste Management, the leading provider of comprehensive waste management services in North America with nearly 26,000 collection and transfer vehicles.     

A constraint programming approach to the Chinese postman problem with time windows

The Chinese postman problem with time windows (CPPTW) is modelled as a constraint programme and results are reported for a set of test problems with up to 69 edges. Two different formulations are proposed. The first formulation approaches the problem directly and the second transforms the problem to an equivalent vehicle routing problem with time windows. The results demonstrate that optimal solutions can be obtained quickly when the time windows are tight. However, the results also show that as the time windows are made wider and the number of feasible solutions increases, these constraint programming formulations take significantly longer to find a provably optimal solution. The results also demonstrate how the size and density of the graph affects the computing time needed to find an optimal solution.     

The vehicle routing problem with multiple prioritized time windows: A case study

This paper addresses Multi-objective Vehicle Routing Problem with Multiple Prioritized Time Windows (VRPMPTW) in which the distributer proposes a set of all non-overlapping time windows with equal or different lengths and the customers prioritize these delivery time windows. VRPMPTW aims to find a set of routes of minimal total traveling cost and maximal customer satisfaction (with regard to the prioritized time windows), starting and ending at the depot, in such a way that each customer is visited by one vehicle given the capacity of the vehicle to satisfy a specific demand. This problem is inspired from a real life application. The contribution of this paper lies in its addressing the VRPMPTW from a problem definition, modeling and methodological point of view. We developed a mathematical model for this problem. This model can simply be used for a wide range of applications where the customers have multiple flexible time windows and violation of time windows may drop the satisfaction levels of customers and lead to profit loss in the long term. A Cooperative Coevolutionary Multi-objective Quantum-Genetic Algorithm (CCMQGA) is also proposed to solve this problem. A new local search is designed and used in CCMQGA to reach an appropriate pareto front. Finally, the proposed approach is employed in a real case study and the results of the proposed CCMQGA are compared with the current solution obtained from managerial experience, the results of NSGA-II and the multi-objective quantum-inspired evolutionary algorithm.     

The pickup and delivery problem with time windows and handling operations

This paper introduces the pickup and delivery problem with time windows and handling operations. In this problem, the loading compartment of a vehicle is modeled as a linear LIFO stack. When an item is picked up, it is positioned on top of the stack. When it is on top of the stack, it can be delivered without additional handling. Otherwise, items on top must be unloaded before the delivery and reloaded afterwards, which requires time. We define two rehandling policies. For both policies, rehandling is only allowed at delivery locations and there is no specific reloading order for the rehandled items. Under the first policy, only compulsory rehandling is allowed. Under the second policy, in addition to compulsory rehandling, preventive rehandling is allowed. For each policy, we propose a branch-price-and-cut algorithm with an ad hoc dominance criterion for the labeling algorithm used to generate routes. Computational results are reported on benchmark instances for the pickup and delivery problem with time windows.     

时间窗约束下的配送车辆调度问题研究

为解决时间窗约束下的物流配送车辆的多目标调度优化问题,给出了一种基于免疫计算的配送车辆调度优化方案。设计了配送车辆调度问题的数学模型和一种基于非劣邻域支配的多目标调度优化算法,在仿真环境下进行了实验。实验结果表明,算法能够有效地解决物流配送车辆调度问题,具有较好的应用价值。     

Exact and heuristic algorithms for the vehicle routing problem with multiple interdependent time windows

In this paper a model and several solution procedures for a novel type of vehicle routing problems where time windows for the pickup of perishable goods depend on the dispatching policy used in the solution process are presented. This problem is referred to as Vehicle Routing Problem with multiple interdependent time windows (VRPmiTW) and is motivated by a project carried out with the Austrian Red Cross blood program to assist their logistics department. Several variants of a heuristic constructive procedure as well as a branch-and-bound based algorithm for this problem were developed and implemented. Besides finding the expected reduction in costs when compared with the current procedures of the Austrian Red Cross, the results show that the heuristic algorithms find solutions reasonably close to the optimum in fractions of a second. Another important finding is that increasing the number of pickups at selected customers beyond the theoretical minimum number of pickups yields significantly greater potential for cost reductions.     

Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm

The present study investigates the cost concerns of distribution centers and formulates a vehicle routing problem with time window constraints accordingly. Based on the embedded structure of the original problem, a decomposition technique is employed to decompose the original problems to a clustering problem (main problem) and a set of traveling salesman problems (sub-problems) with time window constraints. This decomposition not only reduces the problem size but also enable the use of simpler solution procedures. A genetic algorithm is developed to solve the clustering problem, while a simple heuristic algorithm is formulated to solve the set of traveling salesman problems. The solution of the original problem is obtained through iterative interactions between the main problem and the set of sub-problems. The performance of the proposed approach is compared with the well-known insertion method and a manual scheduling of a distribution center.     

Arcs-states models for the vehicle routing problem with time windows and related problems

This paper presents several Arcs-States models that can be applied to numerous vehicle routing problems, one of which is the well-known vehicle routing problem with capacities and time windows. In these models, the variables correspond to the states (i.e. the resource quantities) of the vehicles when they travel through an arc. The LP relaxation of the problem provides a lower bound that can be embedded in a branch and bound algorithm that solves the problem exactly. However, for the pseudo-polynomial number of variables and constraints of our models, column and row generations have to be used. Generally, in a branch and bound algorithm, the lower bound needs to be very efficient to minimize the size of the branch and bound trees as far as possible. One of the models we present, the time-only, relies on a relaxation of the Arcs-States model where a resource is removed from the states in the variables. Although the quality of the bounds decreases, the global resolution time is greatly improved, as illustrated on instances of Solomon's benchmark.     

A bi-objective vehicle routing problem with time windows: A real case in Tenerife

This work is motivated by a real problem posed to the authors by a company in Tenerife, Spain. Given a fleet of vehicles, daily routes have to be designed in order to minimize the total traveled distance while balancing the workload of drivers. This balance has been defined in relation to the length of the routes, regarding to the required time. A bi-objective mixed-integer linear model for the problem is proposed and a solution approach, based on the scatter search metaheuristic, is developed. An extensive computational experience is carried out, using benchmark instances with 25, 50 and 100 customers, to test several components of the proposed method. Comparisons with the exact Pareto fronts for instances up to 25 customers show that the proposed methods obtain good approximations. For comparison purposes, an NSGA-II algorithm has also been implemented. Results obtained on a real case instance are also discussed. In this case, the solution provided by the method proposed in this paper improves the solution implemented by the company.     

A genetic algorithm for the simultaneous delivery and pickup problems with time window

This paper concerns a Simultaneous Delivery and Pickup Problem with Time Windows (SDPPTW). A mixed binary integer programming model was developed for the problem and was validated. Due to its NP nature, a co-evolution genetic algorithm with variants of the cheapest insertion method was proposed to speed up the solution procedure. Since there were no existing benchmarks, this study generated some test problems which revised from the well-known Solomon’s benchmark for Vehicle Routing Problem with Time Windows (VRPTW). From the comparison with the results of Cplex software and the basic genetic algorithm, the proposed algorithm showed that it can provide better solutions within a comparatively shorter period of time.     

A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows

The Vehicle Routing Problem with Time Windows (VRPTW) is a well-known and complex combinatorial problem, which has received considerable attention in recent years. This problem has been addressed using many different techniques including both exact and heuristic methods. The VRPTW benchmark problems of Solomon [Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research 1987; 35(2): 254–65] have been most commonly chosen to evaluate and compare all algorithms. Results from exact methods have been improved considerably because of parallel implementations and modern branch-and-cut techniques. However, 24 out of the 56 high order instances from Solomon's original test set still remain unsolved. Additionally, in many cases a prohibitive time is needed to find the exact solution. Many of the heuristic methods developed have proved to be efficient in identifying good solutions in reasonable amounts of time. Unfortunately, whilst the research efforts based on exact methods have been focused on the total travel distance, the focus of almost all heuristic attempts has been on the number of vehicles. Consequently, it is more difficult to compare and take advantage of the strong points from each approach. This paper proposes a robust heuristic approach for the VRPTW using travel distance as the main objective through an efficient genetic algorithm and a set partitioning formulation. The tests were produced using real numbers and truncated data type, allowing a direct comparison of its results against previously published heuristic and exact methods. Furthermore, computational results show that the proposed heuristic approach outperforms all previously known and published heuristic methods in terms of the minimal travel distance.     

带时间窗口动态车辆路径规划模型及其求解算法

基于事件触发,把带时间窗口动态车辆路径规划问题（DVRPTW）分解成一系列延迟快照,在快照基础上建立相应的动态数学模型,并提出双缓冲区改进大邻域搜索算法进行求解。利用算法的特点,实现新请求无缝插入。采用Solomon设计的56个100节点范例和Lackner相应的动态测试数据,经不同类型动态实例的实验表明,所建立的模型和给出的算法是有效的。     

A column generation approach to extend lifetime in wireless sensor networks with coverage and connectivity constraints

This paper addresses the maximum network lifetime problem in wireless sensor networks with connectivity and coverage constraints. In this problem, the purpose is to schedule the activity of a set of wireless sensors, keeping them connected while network lifetime is maximized. Two cases are considered. First, the full coverage of the targets is required, and second only a fraction of the targets has to be covered at any instant of time. An exact approach based on column generation and boosted by GRASP and VNS is proposed to address both of these problems. Finally, a multiphase framework combining these two approaches is built by sequentially using these two heuristics at each iteration of the column generation algorithm. The results show that our proposals are able to tackle the problem efficiently and that combining the two heuristic approaches improves the results significantly.     

求解带容量和时间窗约束车辆路径问题的改进蝙蝠算法

带时间窗和容量约束的车辆路径问题是车辆路径问题重要的扩展之一,属于NP难题,精确算法的求解效率较低,且对于较大规模问题难以在有限时间内给出最优解.为了满足企业和客户快速有效的配送需求,使用智能优化算法可以在有限的时间内给出相对较优解.研究了求解带容量和时间窗约束车辆路径问题的改进离散蝙蝠算法,为增加扰动机制,提高搜索速...     

A tabu search heuristic for the single vehicle pickup and delivery problem with time windows

The single vehicle pickup and delivery problem with time windows is a generalization of the traveling salesman problem. In such a problem, a number of transportation requests have to be satisfied by one vehicle, each request having constraints to respect: a pickup at its origin and a delivery at its destination, and a time window at each location. The capacity of the vehicle has to be respected. The aim is to minimize the total distance traveled by the vehicle. A number of exact and approximate solution methods exists in the literature, but to the authors knowledge none of them make use of metaheuristics, still promising with other vehicle routing problems. In this paper we present tabu search and probabilistic tabu search. Results obtained on classical traveling salesman problems and a class of randomly generated instances indicate that our approach often produces optimal solutions in a relatively short execution time.     

A vehicle routing problem with pickup and delivery time windows,and coordination of transportable resources

This paper addresses a pickup and delivery problem with time window constraints, using two types of delivery resources, which allows for coordination. A heavy resource (in this case a van) may carry both delivery items and one or more units of the lighter resource (foot couriers) on its single- or multi-route assignment. Foot couriers can pick up and deliver items independently, or travel with a van on its outbound and/or return leg. Coordination between resources can save time and cut costs. The optimization of this type of coordinated logistics system has received scant coverage in the literature. The objective criterion is the total cost (i.e., the sum of fixed cost and travelling cost) of both heavy and light resources. The problem is first formulated as a mixed integer program, assuming a reasonable coordination strategy. A two-stage heuristic is designed by employing both exact approaches and an ejection chain based on modifying the shortest path algorithm implemented in a dynamic network. The two-stage heuristic is compared with optimization models for an independent strategy and a partial coordination strategy on both local and simulated instances of up to 200 customers. Under certain conditions, the benefit of coordination is realized over the independent strategy in terms of lower average total cost and usage of heavy resource.     

A multi-objective dynamic vehicle routing problem with fuzzy time windows: Model,solution and application

In this paper, a multi-objective dynamic vehicle routing problem with fuzzy time windows (DVRPFTW) is presented. In this problem, unlike most of the work where all the data are known in advance, a set of real time requests arrives randomly over time and the dispatcher does not have any deterministic or probabilistic information on the location and size of them until they arrive. Moreover, this model involves routing vehicles according to customer-specific time windows, which are highly relevant to the customers’ satisfaction level. This preference information of customers can be represented as a convex fuzzy number with respect to the satisfaction for a service time. This paper uses a direct interpretation of the DVRPFTW as a multi-objective problem where the total required fleet size, overall total traveling distance and waiting time imposed on vehicles are minimized and the overall customers’ preferences for service is maximized. A solving strategy based on the genetic algorithm (GA) and three basic modules are proposed, in which the state of the system including information of vehicles and customers is checked in a management module each time. The strategy module tries to organize the information reported by the management module and construct an efficient structure for solving in the subsequent module. The performance of the proposed approach is evaluated in different steps on various test problems generalized from a set of static instances in the literature. In the first step, the performance of the proposed approach is checked in static conditions and then the other assumptions and developments are added gradually and changes are examined. The computational experiments on data sets illustrate the efficiency and effectiveness of the proposed approach.