Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints

When vehicle routing problems with additional constraints, such as capacity or time windows, are solved via column generation and branch-and-price, it is common that the pricing subproblem requires the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the vertices. A common solution technique for this problem is dynamic programming. In this paper we illustrate how the basic dynamic programming algorithm can be improved by bounded bi-directional search and we experimentally evaluate the effectiveness of the enhancement proposed. We consider as benchmark problems the elementary shortest path problems arising as pricing subproblems in branch-and-price algorithms for the capacitated vehicle routing problem, the vehicle routing problem with distribution and collection and the capacitated vehicle routing problem with time windows.     

时变单车路径优化模型及动态规划算法

车辆路径问题由于其广泛的应用领域及经济价值而成为学术研究热点。然而,在已有的研究文献中,车辆的速度时变与服务多任务特性很少被关注。本文讨论了具有这两个特性的单车路径优化问题。建立了以送货完成时间最早为优化目标的时变单车送货路径优化模型。由于很难获得该模型的精确解,本文提出了一种贪婪补货策略压缩原问题解空间,设计动态规划算法给出了车辆行驶时间满足FIFO规则的送货顺序近似最优解。数值算例验证了该算法所得到的解仅是原问题的近似最优解这一结论。算例同时表明优化配送时间随着车辆装载能力的增大而缩短,并在车辆装载能力超过所有客户配送总需求时实现最短配送时间,即,使用较大装载能力车辆能节约更多配送时间。     

Two-level evolutionary approach to the survivable mesh-based transport network topological design

The complete topology design problem of survivable mesh-based transport networks is to address simultaneously design of network topology, working path routing, and spare capacity allocation based on span-restoration. Each constituent problem in the complete design problem could be formulated as an Integer Programming (IP) and is proved to be NP\mathcal{NP} -hard. Due to a large amount of decision variables and constraints involved in the IP formulation, to solve the problem directly by exact algorithms (e.g. branch-and-bound) would be impractical if not impossible. In this paper, we present a two-level evolutionary approach to address the complete topology design problem. In the low-level, two parameterized greedy heuristics are developed to jointly construct feasible solutions (i.e., closed graph topologies satisfying all the mesh-based network survivable constraints) of the complete problem. Unlike existing “zoom-in”-based heuristics in which subsets of the constraints are considered, the proposed heuristics take all constraints into account. An estimation of distribution algorithm works on the top of the heuristics to tune the control parameters. As a result, optimal solution to the considered problem is more likely to be constructed from the heuristics with the optimal control parameters. The proposed algorithm is evaluated experimentally in comparison with the latest heuristics based on the IP software CPLEX, and the “zoom-in”-based approach on 28 test networks problems. The experimental results demonstrate that the proposed algorithm is more effective in finding high-quality topologies than the IP-based heuristic algorithm in 21 out of 28 test instances with much less computational costs, and performs significantly better than the “zoom-in”-based approach in 19 instances with the same computational costs.     

Branch-and-price algorithm for a multicast routing problem

This paper considers a multicast routing problem to find the minimum cost tree where the whole communication link delay on each path(route) of the tree is subject to a given delay allowance. The problem is formulated as an integer programming problem by using path variables. An associated problem reduction property is then characterised to reduce the solution space. Moreover, a polynomial time column generation procedure is exploited to solve the associated linear programming relaxation with such solution space reduced. Therefore a branch-and-price algorithm is derived to obtain the optimal integer solution(tree) for the problem. Computational results show that the algorithm can solve practical size problems in a reasonable length of time.     

Fleet assignment and routing with schedule synchronization constraints

This paper introduces a new type of constraints, related to schedule synchronization, in the problem formulation of aircraft fleet assignment and routing problems and it proposes an optimal solution approach. This approach is based on Dantzig–Wolfe decomposition/column generation. The resulting master problem consists of flight covering constraints, as in usual applications, and of schedule synchronization constraints. The corresponding subproblem is a shortest path problem with time windows and linear costs on the time variables and it is solved by an optimal dynamic programming algorithm. This column generation procedure is embedded into a branch and bound scheme to obtain integer solutions. A dedicated branching scheme was devised in this paper where the branching decisions are imposed on the time variables. Computational experiments were conducted using weekly fleet routing and scheduling problem data coming from an European airline. The test problems are solved to optimality. A detailed result analysis highlights the advantages of this approach: an extremely short subproblem solution time and, after several improvements, a very efficient master problem solution time.     

Better Optimization of Nonlinear Uncertain Systems (BONUS): A New Algorithm for Stochastic Programming Using Reweighting through Kernel Density Estimation

Given a series-parallel queueing network topology with exponential servers of finite capacity, a systematic design methodology is presented that approximately solves the optimal routing and buffer space allocation problems within the network. The multi-objective stochastic nonlinear programming problem in integer variables is described and a two-stage iterative optimization procedure is presented which interconnects the routing and buffer space allocation problems. The algorithmic procedure couples the Expansion method, a decomposition method for computing performance measures in queueing networks with finite capacity, along with Powell's unconstrained optimization procedure which allocates the buffers and a multi-variable search procedure for determining the routing probabilities. The effectiveness and efficiency of the resulting two-stage design methodology is tested and evaluated in a series of experimental designs along with simulations of the network topologies.     

Mathematical modelling for optimized control of Moscow's sewer network

An algorithm for the optimized control of a branching urban head-and-gravity sewer network is proposed. The control consists in redistribution of the sewage flows between the network structural components. The algorithm is based on a mathematical model and presupposes the use of a computer. The mathematical model consists of a set of algebraic equations with the structure transporting capacities captured as constraints. The mathematical task of control is stated and solved as an optimization problem. The objective function is the minimization of total electric energy consumption over all the network pumping stations. The assumptions substantiated by practice would reduce the problem to the known problem of linear programming. The discharge through each pumping station of the considered subnetwork of Moscow's sewer network was computed using a mathematical model and was compared to the value observed under the same actual conditions. From this comparison, it was concluded that the proposed algorithm was more successful in controlling the network than was the traditional operation. The correction of the working conditions of some pumping stations of the Moscow sewer subnetwork in accordance with the precalculated time schedule, has allowed a significant decrease in the electric energy consumption for conveyance of the sewage through the network.     

Nodal aggregation of resource constraints in a shortest path problem

The shortest path problem with resource constraints consists of finding the minimum cost path between two specified points while respecting constraints on resource consumption. Its solving by a dynamic programming algorithm requires a computation time increasing with the number of resources. With the aim of producing rapidly a good heuristic solution we propose to reduce the state space by aggregating resources. Our approach consists of projecting the resources on a vector of smaller dimension and then to dynamically adjust the projection matrix to get a better approximation of the optimal solution. We propose an adjustment based on Lagrangian and surrogate relaxations in a column generation framework, in which the sub-problems are shortest path problems with resource constraints. We adjust the multipliers only one time at each column generation iteration. This permit to obtain good solutions of the scheduling problem in few time.     

A path relinking algorithm for a multi-depot periodic vehicle routing problem

In this paper, we consider a multi-depot periodic vehicle routing problem which is characterized by the presence of a homogeneous fleet of vehicles, multiple depots, multiple periods, and two types of constraints that are often found in reality, i.e., vehicle capacity and route duration constraints. The objective is to minimize total travel costs. To tackle the problem, we propose an efficient path relinking algorithm whose exploration and exploitation strategies enable the algorithm to address the problem in two different settings: (1) As a stand-alone algorithm, and (2) As a part of a co-operative search algorithm called integrative co-operative search. The performance of the proposed path relinking algorithm is evaluated, in each of the above ways, based on standard benchmark instances. The computational results show that the developed PRA performs well, in both solution quality and computational efficiency.     

An Online Actor–Critic Algorithm with Function Approximation for Constrained Markov Decision Processes

We develop an online actor–critic reinforcement learning algorithm with function approximation for a problem of control under inequality constraints. We consider the long-run average cost Markov decision process (MDP) framework in which both the objective and the constraint functions are suitable policy-dependent long-run averages of certain sample path functions. The Lagrange multiplier method is used to handle the inequality constraints. We prove the asymptotic almost sure convergence of our algorithm to a locally optimal solution. We also provide the results of numerical experiments on a problem of routing in a multi-stage queueing network with constraints on long-run average queue lengths. We observe that our algorithm exhibits good performance on this setting and converges to a feasible point.     

Time Optimal Path Planning for Industrial Robots: A Dynamic Programming Approach Considering Torque Derivative and Jerk Constraints

This paper presents a dynamic programming approach for calculating time optimal trajectories for industrial robots, subject to various physical constraints. In addition to path velocity, motor torque, joint velocity and acceleration constraints, the present contribution also shows how to deal with torque derivative and joint jerk limitations. First a Cartesian path for the endeffector is defined by splines using Bernstein polynomials as basis functions and is parameterized via a scalar path parameter. In order to compute the belonging quantities in configuration space, inverse kinematics is solved numerically. Using this and in combination with the dynamical model, joint torques as well as their derivatives can be constrained. For that purpose the equations of motion are calculated with the help of the Projection Equation. As a consequence of the used optimization problem formulation, the dynamical model as well as the restrictions have to be transformed to path parameter space. Due to the additional consideration of jerk and torque derivative constraints, the phase plane is expanded to a phase space. The parameterized restrictions lead to feasible regions in this space, in which the optimal solution is sought. Result of the optimization is the time behavior of the path parameter and subsequently the feed forward torques for the optimal motion on the spatial path defined by previously mentioned splines. Simulation results as well as experimental results for a three axes industrial robot are presented. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

计及多重阻塞的电动汽车移动储能特性建模

为实现城市交通电力耦合系统在城市道路、充电设施、输电线路阻塞环境下的优化运行,提出了计及多重阻塞的动态交通电力流联合优化方法。首先,基于时空网络模型,提出了计及电动汽车移动、静止、充电、排队模式的队列时空网络模型,构建了适用于电动汽车的车辆调度模型,进而形成动态交通分配模型,以减少交通出行损失。其次,通过优化发电机组、储能等的出力和备用计划,计及城市电网安全、备用约束,构建了安全约束动态经济调度模型,以降低碳排放及发电成本。随后,形成多目标动态优化模型,并将其转换为混合整数凸二次规划问题。最后,在耦合IEEE-30、Sioux Falls系统中验证了所提模型的有效性。     

The vehicle routing problem with flexible time windows and traveling times

We generalize the standard vehicle routing problem by allowing soft time window and soft traveling time constraints, where both constraints are treated as cost functions. With the proposed generalization, the problem becomes very general. In our algorithm, we use local search to determine the routes of vehicles. After fixing the route of each vehicle, we must determine the optimal start times of services at visited customers. We show that this subproblem is NP-hard when cost functions are general, but can be efficiently solved with dynamic programming when traveling time cost functions are convex even if time window cost functions are non-convex. We deal with the latter situation in the developed iterated local search algorithm. Finally we report computational results on benchmark instances, and confirm the benefits of the proposed generalization.     

The mixed capacitated general routing problem under uncertainty

We study the General Routing Problem defined on a mixed graph and with stochastic demands. The problem under investigation is aimed at finding the minimum cost set of routes to satisfy a set of clients whose demand is not deterministically known. Since each vehicle has a limited capacity, the demand uncertainty occurring at some clients affects the satisfaction of the capacity constraints, that, hence, become stochastic. The contribution of this paper is twofold: firstly we present a chance-constrained integer programming formulation of the problem for which a deterministic equivalent is derived. The introduction of uncertainty into the problem poses severe computational challenges addressed by the design of a branch-and-cut algorithm, for the exact solution of limited size instances, and of a heuristic solution approach exploring promising parts of the search space. The effectiveness of the solution approaches is shown on a probabilistically constrained version of the benchmark instances proposed in the literature for the mixed capacitated general routing problem.     

Arc routing problems with time-dependent service costs

This paper studies an arc routing problem with capacity constraints and time-dependent service costs. This problem is motivated by winter gritting applications where the “timing” of each intervention is crucial. The exact problem-solving approach reported here first transforms the arc routing problem into an equivalent node routing problem. Then, a column generation scheme is used to solve the latter. The master problem is a classical set covering problem, while the subproblems are time-dependent shortest path problems with resource constraints. These subproblems are solved using an extension of a previously developed algorithm. Computational results are reported on problems derived from a set of classical instances of the vehicle routing problem with time windows.     

Lower and upper bounds for location-arc routing problems with vehicle capacity constraints

This paper addresses multi-depot location arc routing problems with vehicle capacity constraints. Two mixed integer programming models are presented for single and multi-depot problems. Relaxing these formulations leads to other integer programming models whose solutions provide good lower bounds for the total cost. A powerful insertion heuristic has been developed for solving the underlying capacitated arc routing problem. This heuristic is used together with a novel location–allocation heuristic to solve the problem within a simulated annealing framework. Extensive computational results demonstrate that the proposed algorithm can find high quality solutions. We also show that the potential cost saving resulting from adding location decisions to the capacitated arc routing problem is significant.     

时变条件下带时间窗车辆调度问题的模拟退火算法

带时间窗车辆调度问题(VRPTW)是一类要求满足容积和时间窗约束的车辆路径优化问题,现 有大部分相关文献只考虑了车辆行驶速度恒定的情况,忽略了各种动态因素的影响.本文研究的时变条件下带时间窗车辆调度问题将车辆行驶速度考虑成时变分段函数,并利用模拟退火算法进行求解,最后通过实验结果说明算法的有效性.     

Virtual path layouts optimizing total hop count on ATM tree networks

This paper presents some algorithmic results concerning virtual path layouts for the one-to-many communication problem in ATM tree networks. The ATM network model is based on covering the network with a layout of virtual paths, under some constraints on the allowed load, namely, the number of paths that can share an edge. The quality measure used is the hop count, namely, the number of edges traversed between two vertices that need to communicate. Whereas most former results concerned the maximum hop count of the virtual path layout, our interest here is in measuring its total hop count, or alternatively its average hop count. The paper presents a dynamic programming algorithm for planning ATM network layouts with minimal total hop count for one-to-many requirements under load constraints over the class of tree networks.     

基于遗传算法的二层线性规划问题的求解算法

本研究了下层以最优解返回上层的二层线性规划问题的遗传算法。在提出可行度概念的基础上，构造了二层线性规划上层规划问题的适应度函数，由此设计了求解二层线性规划问题遗传算法。为了提高遗传算法处理约束的能力，在产生初始种群时将随机产生的初始种群变为满足约束的初始种群，从而避免了使用罚函数处理约束带来的困难，最后用实例验证了本提出的二层线性规划的遗传算法的有效性。     

Constraint Programming Based Column Generation for Crew Assignment

Airline crew assignment problems are large-scale optimization problems which can be adequately solved by column generation. The subproblem is typically a so-called constrained shortest path problem and solved by dynamic programming. However, complex airline regulations arising frequently in European airlines cannot be expressed entirely in this framework and limit the use of pure column generation. In this paper, we formulate the subproblem as a constraint satisfaction problem, thus gaining high expressiveness. Each airline regulation is encoded by one or several constraints. An additional constraint which encapsulates a shortest path algorithm for generating columns with negative reduced costs is introduced. This constraint reduces the search space of the subproblem significantly. Resulting domain reductions are propagated to the other constraints which additionally reduces the search space. Numerical results based on data of a large European airline are presented and demonstrate the potential of our approach.