A Combined column generation and heuristics for railway short-term rolling stock planning with regular inspection constraints

The aim of railway rolling stock planning problem is to find an optimal allocation of train-sets for a given set of trips in the train timetable in order to minimize the total cost. We propose a column generation and Lagrangian relaxation heuristics for short-term rolling stock planning problems with regular inspection constraints. The problem is formulated as a subtour traveling salesman problem to find a set of elementary shortest cycles that cover all trips in the timetable. In the proposed method, a tight lower bound is obtained from the continuous relaxation of Dantzig–Wolfe reformulation by column generation. The pricing problem can be formulated as an elementary shortest cycle problem with resource constraints. A labeling algorithm is applied to solve the pricing problem. In order to reduce the computational effort, we apply a general state space augmenting algorithm to solve the pricing problems. Computational results show that the proposed column generation and Lagrangian relaxation heuristics can find good lower and upper bounds for 300 trips within reasonable computing time.     

A strong flow-based formulation for the shortest path problem in digraphs with negative cycles

In this paper, we are interested in the shortest path problem between two specified vertices in digraphs containing negative cycles. We study two integer linear formulations and their linear relaxations. A first formulation, close in spirit to a classical formulation of the traveling salesman problem, requires an exponential number of constraints. We study a second formulation that requires a polynomial number of constraints and, as confirmed by computational experiments, its linear relaxation is significantly sharper. From the second formulation we propose a family of linear relaxations with fewer variables than the classical linear one.     

有向黑白旅行商问题

黑白旅行商问题是经典旅行商问题的推广,在基于SONET技术的光纤网络设计、航线调度等领域具有广泛的应用.已有研究工作集中在无向黑白旅行商问题上.文章研究该问题的更一般形式--有向黑白旅行商问题.首先,给出了有向黑白旅行商问题的混合整数线性规划公式.与目前无向黑白旅行商问题包含指数多个约束的规划公式相比,它仅包含多项式个约束.其次,给出了一种启发式算法.实验表明,该启发式算法能够有效地求解黑白旅行商问题的实例.由于无向黑白旅行商问题是有向黑白旅行商问题的特例,故文中的结论对于求解无向黑白旅行商问题同样有效.     

Lagrangian duality applied to the vehicle routing problem with time windows

This paper considers the vehicle routing problem with time windows, where the service of each customer must start within a specified time interval. We consider the Lagrangian relaxation of the constraint set requiring that each customer must be served by exactly one vehicle yielding a constrained shortest path subproblem. We present a stabilized cutting-plane algorithm within the framework of linear programming for solving the associated Lagrangian dual problem. This algorithm creates easier constrained shortest path subproblems because less negative cycles are introduced and it leads to faster multiplier convergence due to a stabilization of the dual variables. We have embedded the stabilized cutting-plane algorithm in a branch-and-bound search and introduce strong valid inequalities at the master problem level by Lagrangian relaxation. The result is a Lagrangian branch-and-cut-and-price (LBCP) algorithm for the VRPTW. Making use of this acceleration strategy at the master problem level gives a significant speed-up compared to algorithms in the literature based on traditional column generation. We have solved two test problems introduced in 2001 by Gehring and Homberger with 400 and 1000 customers respectively, which to date are the largest problems ever solved to optimality. We have implemented the LBCP algorithm using the ABACUS open-source framework for solving mixed-integer linear-programs by branch, cut, and price.     

Exact Solution of Cutting Stock Problems Using Column Generation and Branch-and-Bound

This paper describes an attempt to solve the one-dimensional cutting stock problem exactly, using column generation and branch-and-bound. A new formulation is introduced for the one-dimensional cutting stock problem that uses general integer variables, not restricted to be binary. It is an arc flow formulation with side constraints, whose linear programming relaxation provides a strong lower bound. In this model, a cutting pattern, which corresponds to a path, is decomposed into single arc variables. The decomposition serves the purpose of showing that it is possible to combine the branch-and-bound method with variable generation. Computational times are reported for one-dimensional cutting stock instances with a number of orders up to 30.     

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.     

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 hub location problem with fully interconnected backbone and access networks

This paper considers the design of two-layered fully interconnected networks. A two-layered network consists of clusters of nodes, each defining an access network and a backbone network. We consider the integrated problem of determining the access networks and the backbone network simultaneously. A mathematical formulation is presented, but as the linear programming relaxation of the mathematical formulation is weak, a formulation based on the set partitioning model and column generation approach is also developed. The column generation subproblems are solved by solving a series of quadratic knapsack problems. We obtain superior bounds using the column generation approach than with the linear programming relaxation. The column generation method is therefore developed into an exact approach using the branch-and-price framework. With this approach we are able to solve problems consisting of up to 25 nodes in reasonable time. Given the difficulty of the problem, the results are encouraging.     

$K$ Constrained Shortest Path Problem

Motivated by a real project for a sophisticated automated storage and retrieval system (AS/RS), we study the problem of generating K shortest paths that are required to satisfy a set of constraints. We propose a structural branching procedure that decomposes the problem into at most K|N| subproblems, where |N| is the number of nodes in the network. By using a Network Modification procedure, each subproblem can be transformed into a constrained shortest path problem (CSP). When these constraints satisfy a so called separable property, the subproblem can be further simplified. Based on this branching procedure, we propose a specific algorithm for an application where resource and loopless constraints have to be respected. Numerical results show that our algorithm is very efficient and robust.     

启发式列生成算法求解带恶化效应的同构并行机调度问题

针对实际生产中广泛存在的一类带恶化效应的同构并行机调度问题,以最小化最大完工时间为优化目标,构建该问题的整数规划模型,并提出一种启发式列生成算法(HCGA)进行求解.在HCGA中,首先,利用Dantzig-Wolfe分解方法,将原问题分解为一个主问题(MP)和多个子问题;然后,设计启发式算法获得初始列,其中每列为一台机器上的一个调度方案,基于初始列构建限制主问题(RMP)模型;接着,设计快速有效的动态规划算法求解子问题,以得到需添加至RMP的列集,同时,考虑传统列生成算法收敛速度较慢,设计一系列方法来加速列生成过程;最后,基于所获取的MP线性松弛解,设计深潜启发式算法确定原问题的整数解.HCGA与商用求解器GUROBI的对比实验结果表明,HCGA可在较短时间内获得更优的解.     

旅行商问题的DNA算法

旅行商问题是求仅一次遍访指定城市并返回出发城市的最短旅行路线的问题,它是图论中一个经典的NP完全问题,用电子计算机需要指数级的时间才能得到解决,该文基于分子生物技术并利用Adleman-Lipton模型给出旅行商问题的DNA算法,这个DNA算法理论上能在多项式的时间内解决这个NP完全问题。具体地对n个城市的旅行商问题,首先将它视为一个具有顶点和边的图,并将顶点、边分别用DNA链编码表示,边的方向通过顶点的编码获得;再将这些DNA链投放在试管中进行生物化学反应,利用DNA计算的高效并行性,通过基本的生物实验操作最后得到旅行商问题的解,其过程的复杂度为O(n)。该算法的创新之处在于表示城市和路径的DNA链长度的设计,能使我们在合理小的范围内寻找旅行商问题的解,较大地简化了问题的复杂度。     

A comparison of algorithms for origin–destination matrix generation on real road networks and an approximation approach

This paper considers the generation of the origin–destination (OD) matrix, basic data in any vehicle routing or traveling salesman problem. An OD matrix must be generated by calculating the shortest paths between some nodes. Candidate methods for this are repetitive use of one-to-all shortest path algorithms such as Dijkstra’s algorithm, use of all-to-all shortest path algorithms such as the Floyd–Warshall algorithm, and use of specifically designed some-to-some shortest path algorithms. This paper compares the performance of several shortest path algorithms in computing OD matrices on real road networks. Dijkstra’s algorithm with approximate bucket data structure performed the best for most of the networks tested. This paper also proposes a grouping-based algorithm for OD matrix generation. Although it is an approximation approach, it has several good characteristics: it can find the exact shortest distances for most OD pairs; it guarantees that all the calculated shortest path distance values have corresponding paths; the deviation of any distance from the corresponding true shortest distance is small; and its computation time is short.     

An Algorithm for the One Commodity Pickup and Delivery Traveling Salesman Problem with Restricted Depot

In this paper we study the one commodity pickup-and-delivery traveling salesman problem with restricted depot (1-PDTSP-RD), which is a generalization of the classical traveling salesman problem (TSP). We first introduce a polynomial size integer programming formulation for the problem and then study the feasibility issue which is shown to be \(\mathcal {NP}\)-complete by itself. In particular, we prove sufficient conditions for the feasibility of the problem and provide a polynomial algorithm to find a feasible solution. We also develop a bound on the cost of the 1-PDTSP-RD solution in terms of the cost of the TSP solution. Based on this bound, we provide a heuristic algorithm to solve the 1PDTSP-RD. Extensive numerical experiments are performed to evaluate the efficiency of both the exact and approximation algorithms.     

Optimized Scheduled Multiple Access Control for Wireless Sensor Networks

We consider wireless sensor networks with multiple sensor modalities that capture data to be transported over multiple frequency channels to potentially multiple gateways. We study a general problem of maximizing a utility function of achievable transmission rates between communicating nodes. Decisions involve routing, transmission scheduling, power control, and channel selection, while constraints include physical communication constraints, interference constraints, and fairness constraints. Due to its structure the formulation grows exponentially with the size of the network. Drawing upon large-scale decomposition ideas in mathematical programming, we develop a cutting-plane algorithm and show that it terminates in a finite number of iterations. Every iteration requires the solution of a subproblem which is NP-hard. To solve the subproblem we i) devise a particular relaxation that is solvable in polynomial time and ii) leverage polynomial-time approximation schemes. A combination of both approaches enables an improved decomposition algorithm which is efficient for solving large problem instances.      

基于GA的MTSP问题的研究

目前对于旅行商问题的研究已经到了一个比较成熟的阶段,但是对于多旅行商问题的研究还相对较少。文章针对使所有旅行商路程尽可能平均（即所有旅行商路程的最大值最小）,且所有旅行商的总路程最小的一类多旅行商问题进行研究,通过三交换启发式交叉算子,变换变异算子和矩阵解码方法来优化简单的遗传算法。最后通过仿真试验,验证了该算法的有效性和可行性。     

A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup times

This paper introduces and compares three different formulations of a production scheduling problem with sequence-dependent and time-dependent setup times on a single machine. The setup is divided into two parts: one that can be performed at any time and another one that is restricted to be performed outside of a given time interval. As a result, the setup time between two jobs is a function of the completion time of the first job. The problem can be formulated as a time-dependent traveling salesman problem, where the travel time between two nodes is a function of the departure time from the first node. We show that the resulting formulation can be strengthened to provide better linear programming relaxation lower bounds. We also introduce several families of valid inequalities which are used within a branch-and-cut algorithm. Computational experiments show that this algorithm can solve some instances with up to 50 jobs within reasonable computing times.     

Randomized heuristics for the family traveling salesperson problem

This paper introduces the family traveling salesperson problem (FTSP), a variant of the generalized traveling salesman problem. In the FTSP, a subset of nodes must be visited for each node cluster in the graph. The objective is to minimize the distance traveled. We describe an integer programming formulation for the FTSP and show that the commercial grade integer programming solver CPLEX 11 can only solve small instances of the problem in reasonable running time. We propose two randomized heuristics for finding optimal and near‐optimal solutions of this problem. These heuristics are a biased random‐key genetic algorithm and a GRASP with evolutionary path‐relinking. Computational results comparing both heuristics are presented in this study.     

A hybrid genetic algorithm for no-wait job shop scheduling problems

A no-wait job shop (NWJS) describes a situation where every job has its own processing sequence with the constraint that no waiting time is allowed between operations within any job. A NWJS problem with the objective of minimizing total completion time is a NP-hard problem and this paper proposes a hybrid genetic algorithm (HGA) to solve this complex problem. A genetic operation is defined by cutting out a section of genes from a chromosome and treated as a subproblem. This subproblem is then transformed into an asymmetric traveling salesman problem (ATSP) and solved with a heuristic algorithm. Subsequently, this section with new sequence is put back to replace the original section of chromosome. The incorporation of this problem-specific genetic operator is responsible for the hybrid adjective. By doing so, the course of the search of the proposed genetic algorithm is set to more profitable regions in the solution space. The experimental results show that this hybrid genetic algorithm can accelerate the convergence and improve solution quality as well.     

指针网络改进遗传算法求解旅行商问题

虽然遗传算法相较于其他算法能够更好地求解旅行商问题,但这种算法在使用的过程中容易陷入局部最优的问题,进而导致问题求解遭遇困境。文章在简要介绍旅行商问题的基础上,介绍了遗传算法求解旅行商问题的思路和方法,并明确算法应用中存在的不足。在此基础上提出基于指针网络改进遗传算法求解旅行商问题的新思路,为弥补遗传算法的缺陷提供相应的原理支持。     

Visiting convex regions in a polygonal map

This paper is concerned with a variant of the multi-goal path planning in which goals are represented as convex polygons. The problem is to find a closed shortest path in a polygonal map such that all goals are visited. The proposed solution is based on a self-organizing map (SOM) algorithm for the traveling salesman problem. Neurons’ weights are considered as nodes inside the polygonal domain and connected nodes represent a path that evolves according to the proposed adaptation rules. In addition, a reference algorithm based on the solution of the traveling salesman problem and the consecutive touring polygons problem is provided to find high quality solutions of the created set of problems. The problems are designed to represent various inspection and patrolling tasks and can form a kind of benchmark set for multi-goal path planning algorithms. The performance of the algorithms is examined in this problem set, which includes an instance of the watchman route problem with restricted visibility range. The proposed SOM based algorithms provide a unified approach to solve various visibility based routing problems in polygonal maps while they provide a competitive quality of solutions to the reference algorithm with significantly lower computational requirements.