Skewed general variable neighborhood search for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem (CCVRP) is a relatively new version of the classical capacitated vehicle routing problem, and it is equivalent to a traveling repairman problem with capacity constraints and a homogeneous vehicle fleet, which aims to minimize the total arrival time at customers. Many real‐world applications can be modeled by this problem, such as the important application resulting from the humanitarian aid following a natural disaster. In this paper, two heuristics are proposed. The first one is a constructive heuristic to generate an initial solution and the second is the skewed variable neighborhood search (SVNS) heuristic. The SVNS algorithm starts with the initial solution. At each iteration, the perturbation phase and the local search phase are used to improve the solution of the CCVRP, and the distance function in acceptance criteria phase is used to improve the exploration of faraway valleys. This algorithm is applied to a set of benchmarks, and the comparison results show that the proposed algorithms provide better solutions than those reported in the previous literature on memetic algorithms and adaptive large neighborhood search heuristics.     

Hybrid methods for lot sizing on parallel machines

We consider the capacitated lot sizing problem with multiple items, setup time and unrelated parallel machines, and apply Dantzig–Wolfe decomposition to a strong reformulation of the problem. Unlike in the traditional approach where the linking constraints are the capacity constraints, we use the flow constraints, i.e. the demand constraints, as linking constraints. The aim of this approach is to obtain high quality lower bounds. We solve the master problem applying two solution methods that combine Lagrangian relaxation and Dantzig–Wolfe decomposition in a hybrid form. A primal heuristic, based on transfers of production quantities, is used to generate feasible solutions. Computational experiments using data sets from the literature are presented and show that the hybrid methods produce lower bounds of excellent quality and competitive upper bounds, when compared with the bounds produced by other methods from the literature and by a high-performance MIP software.     

An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem (CCVRP) is a variation of the classical capacitated vehicle routing problem in which the objective is the minimization of the sum of arrival times at customers, instead of the total routing cost. This paper presents an adaptive large neighborhood search heuristic for the CCVRP. This algorithm is applied to a set of benchmark instances and compared with two recently published memetic algorithms.     

Computationally efficient solution of the multi-item, capacitated lot-sizing problem

The problem of multi-item, single-level, dynamic lotsizing in the presence of a single capacitated resource is addressed. A model based on variable redefinition is developed leading to a solution strategy based on a branch-and-bound search with sharp low bounds. The multi-item low bound problems are solved by column generation with the capacity constraints as the linking constraints. The resulting subproblems separate into as many single-item, uncapacitated lotsizing problems as there are items. These subproblems are solved as shortest-path problems. Good upper bounds are also generated by solving an appropriate minimum-cost network flow problem at each node of the branch-and-bound tree. The resulting solution scheme is very efficient in terms of computation time. Its efficiency is demonstrated by computational testing on a ste of benchmark problem instances and is attributable to the sharpness of the lower bounds, the efficiency with which the low bound problems are solved and the frequent generation of good upper bounds; all of which leading to a high exclusion rate.     

On the optimality of facility location for wireless transmission infrastructure

The location and configuration of transmission infrastructure for cellular wireless communication networks is a complex engineering task involving competing objectives. While minimizing the number of locations used, adequate area coverage is required in addition to satisfying constraints concerning capacity and interference.We focus on the problem of commissioning omni-directional transmission equipment. This is particularly relevant to operators in the initial stages of network rollout. We address the problem of finding lower bounds on the minimum number of sites. An efficient technique for obtaining improved lower bounds on the minimum number of sites required for area coverage is presented. This approach also takes into account user-defined interference and capacity constraints. Additionally, we present a unifying framework for cell planning when site selection and power configuration is required. Detailed computational results are presented and discussed.     

Design of robust H ∞ controller for a half-vehicle active suspension system with input delay

This article is concerned with the problem of robust H _∞ control for a half-vehicle active suspension system with input delay. The delay is assumed to be interval time-varying delay with unknown derivative. The vehicle front sprung mass and the rear unsprung mass are assumed to be varying due to vehicle load variation and may result in parameter uncertainties being modelled by polytopic uncertainty. First of all, regarding the heave and pitch accelerations as the optimisation objectives, and suspension deflection and relative tire load constraints as the output constraints, we build the corresponding suspension systems. Then, by constructing a novel Lyapunov functional involved with the lower and upper bounds of the delay, sufficient condition for the existence of robust H _∞ controller is given to ensure robust asymptotical stability of the closed-loop system and also guarantee the constrained performance. The condition can be converted into convex optimisation problem and verified easily by means of standard software. Finally, a design example is exploited to demonstrate the effectiveness of the proposed design method.     

The pursuit-evasion problem under integral-geometric constraints on pursuer controls

We study the pursuit-evasion problem for a model game with simple motions when pursuer controls are subject to both integral and geometric constraints while evader controls are only subject to geometric ones. Depending on initial conditions of the players and parametric values participating in control constraints, we prove the theorem of alternative. To solve the pursuit problem, we propose a parallel pursuit strategy (Π-strategy) that ensures optimal convergence of the players and study its structure depending on the parameters. To solve the evasion problem, we find lower bounds on the convergence that also depend on given parameters. This work develops and extends the works of Isaacs, Petrosyan, Pshenichnyi and other researchers, including the author.     

The open capacitated arc routing problem

The Open Capacitated Arc Routing Problem (OCARP) is a NP-hard combinatorial optimization problem where, given an undirected graph, the objective is to find a minimum cost set of tours that services a subset of edges with positive demand under capacity constraints. This problem is related to the Capacitated Arc Routing Problem (CARP) but differs from it since OCARP does not consider a depot, and tours are not constrained to form cycles. Applications to OCARP from literature are discussed. A new integer linear programming formulation is given, followed by some properties of the problem. A reactive path-scanning heuristic, guided by a cost-demand edge-selection and ellipse rules, is proposed and compared with other successful CARP path-scanning heuristics from literature. Computational tests were conducted using a set of 411 instances, divided into three classes according to the tightness of the number of vehicles available; results reveal the first lower and upper bounds, allowing to prove optimality for 133 instances.     

用于求解混合车辆路径问题的混合进化算法

文中研究了具有NP难度的混合车辆路径问题(Mixed Capacitated General Routing Problem,MCGRP),其是在基本车辆路径问题(Vehicle Routing Problem,VRP)的基础上通过添加限载容量约束及弧上的用户需求而衍生的。给定一列车辆数不限的车队,使车辆从站点出发向用户提供服务,服务完用户需求后仍返回站点;规定每辆车的总载重不能超过其载重量,且每个需求只能被一辆车服务且仅服务一次。MCGRP旨在求解每辆车的服务路线,使得在满足以上约束条件的情况下所有车辆的旅行消耗之和最小。混合车辆路径问题具有较高的理论价值和实际应用价值,针对该问题提出了一种高效的混合进化算法。该算法采用基于5种邻域算符的变邻域禁忌搜索来提高解的质量,并通过一种基于路径的交叉算符来继承解的优异性,从而有效地加速算法的收敛。在一组共计23个经典算例上的实验结果表明,该混合进化算法在求解混合车辆路径问题时是非常高效的。     

基于改进粒子群算法的物流配送车辆调度

物流配送车辆调度问题是指安排有限的车辆有效地完成配送任务。优化目标是在满足客户需求和车辆能力约束的条件下,找出配送成本较低的配送车辆调度方案。由于配送过程受客户位置、配送车辆限制等多种因素影响,导致车辆的调度问题十分复杂。参照经典车辆路径问题模型,考虑了车辆配送里程和用户数等限制,建立了双向车辆调度问题的数学模型。在标准粒子群算法的基础上,引入爬山操作,增加了粒子群的多样性,提高了算法的局部搜索能力,并设计了基于改进粒子群算法的物流配送车辆调度算法,有效地解决了物流配送车辆的优化调度问题。     

The undirected capacitated arc routing problem with profits

A profit and a demand are associated with each edge of a set of profitable edges of a given graph. A travel time is associated with each edge of the graph. A fleet of capacitated vehicles is given to serve the profitable edges. A maximum duration of the route of each vehicle is also given. The profit of an edge can be collected by one vehicle only that also serves the demand of the edge. The objective of this problem, which is called the undirected capacitated arc routing problem with profits (UCARPP), is to find a set of routes that satisfy the constraints on the duration of the route and on the capacity of the vehicle and maximize the total collected profit. We propose a branch-and-price algorithm and several heuristics. We can solve exactly instances with up to 97 profitable edges. The best heuristics find the optimal solution on most of instances where it is available.     

Interior‐Point Method to Optimize Tire Force Allocation in 4‐Wheeled Vehicles Using High‐Level Sliding Mode Control with Adaptive Gain

Nonlinear vehicle control allocation is achieved by distributing the control task to tire forces with nonlinear saturation constraints. The overall vehicle control is accomplished by developing a hierarchical scheme. First, a high‐level sliding mode control with adaptive gain is considered to obtain the body force/moment for stable vehicle motion. The proposed controller only requires online adaptation of control gains without acquiring the knowledge of upper‐bounds on system uncertainties. Then, optimal distribution of tire forces (ODF) with nonlinear saturation constraints is considered. The high‐level control objectives are mapped to individual tire forces by formulating a nonlinear optimization problem. The interior‐point (IP) method is adopted for a nonlinear programming task at each time step. Evaluation of the overall system is accomplished by simulation testing with a nine‐degrees‐of‐freedom vehicle nonlinear model. Comparison with a well‐recognized control system shows the effect of saturation constrained ODF (SCODF) on improving vehicle handling and stability.     

修改D-W分解求具有需求时间窗和投机性成本的批量问题

研究多产品具有能力约束、需求时间窗、允许延期交货和投机性成本的批量问题.分析无能力约束凸包极点的特征,采用修正的Dantzig-Wolfe分解对原问题进行等价变换.使用列生成获得下界,同时采用启发式分支定界寻找近优解.对随机算例进行了测试与比较,计算结果表明上界与下界之间的间隙非常小;另外分析了当能力参数和订单规模变化时解的质量和计算时间.     

Fast approximate clearance evaluation for rovers with articulated suspension systems

We present a light‐weight body‐terrain clearance evaluation algorithm for the automated path planning of NASA's Mars 2020 rover. Extraterrestrial path planning is challenging due to the combination of terrain roughness and severe limitation in computational resources. Path planning on cluttered and/or uneven terrains requires repeated safety checks on all the candidate paths at a small interval. Predicting the future rover state requires simulating the vehicle settling on the terrain, which involves an inverse‐kinematics problem with iterative nonlinear optimization under geometric constraints. However, such expensive computation is intractable for slow spacecraft computers, such as RAD750, which is used by the Curiosity Mars rover and upcoming Mars 2020 rover. We propose the approximate clearance evaluation (ACE) algorithm, which obtains conservative bounds on vehicle clearance, attitude, and suspension angles without iterative computation. It obtains those bounds by estimating the lowest and highest heights that each wheel may reach given the underlying terrain, and calculating the worst‐case vehicle configuration associated with those extreme wheel heights. The bounds are guaranteed to be conservative, hence ensuring vehicle safety during autonomous navigation. ACE is planned to be used as part of the new onboard path planner of the Mars 2020 rover. This paper describes the algorithm in detail and validates our claim of conservatism and fast computation through experiments.     

Minimum–Maximum regret redundancy allocation with the choice of redundancy strategy and multiple choice of component type under uncertainty

This paper deals with a redundancy allocation problem in series–parallel systems with the choice of redundancy strategy, including active and cold standby strategies in which component’s time to failure follows an Erlang distribution. The scale parameter of Erlang distribution and consequently the reliability of each component are imprecise in terms of interval data, and only the lower and upper bounds are known. This problem, for the first time, is formulated through Min–Max regret criterion, which is commonly used to define robust solutions. The resulting problem formulation contains an unlimited number of constraints, and a Benders’ decomposition method is implemented to deal with the given problem. This method is compared with an enumeration method to show its effectiveness. The performance of the proposed model using the Benders’ decomposition method is examined over different problem sizes, and the associated results are analyzed.     

Solving large-scale linear programs by aggregation

This paper deals with the solution of linear programs via the use of aggregation. A sequence of smaller, aggregated problems are solved. At each iteration we develop lower and upper bounds on the objective value. If the solution is not acceptable, a scheme for modifying the aggregated problem is given. The procedure is computationally tested on problems with up to 200 variables/constraints.     

Solving a rich vehicle routing and inventory problem using column generation

The livestock collection problem (LCP) is a rich vehicle routing problem (VRP) extended with inventory constraints. The LCP is a complex planning problem taken from the meat industry, and the goal is to construct a set of vehicle routes to collect animals from farms for slaughter at a slaughterhouse. Several constraints dealing with animal welfare are added, some of these lead to a loading problem where the vehicle capacity depends on the loading sequence. In addition, global constraints to handle production and inventory at the slaughterhouse are needed. This paper presents an exact solution method for the LCP, based on column generation, that solves much larger instances to optimality than what has been done before. The algorithm presented here also solves a richer model that is closer to the underlying real-world problem than previously published work on exact methods for this problem is based on.     

An Algorithm to Decide Feasibility of Linear Integer Constraints Occurrng in Decision Tables

To detect errors in decision tables one needs to decide whether a given set of constraints is feasible or not. This paper describes an algorithm to do so when the constraints are linear in variables that take only integer values. Decision tables with such constraints occur frequently in business data processing and in nonnumeric applications. The aim of the algorithm is to exploit. the abundance of very simple constraints that occur in typical decision table contexts. Essentially, the algorithm is a backtrack procedure where the the solution space is pruned by using the set of simple constrains. After some simplications, the simple constraints are captured in an acyclic directed graph with weighted edges. Further, only those partial vectors are considered from extension which can be extended to assignments that will at least satisfy the simple constraints. This is how pruning of the solution space is achieved. For every partial assignment considered, the graph representation of the simple constraints provides a lower bound for each variable which is not yet assigned a value. These lower bounds play a vital role in the algorithm and they are obtained in an efficient manner by updating older lower bounds. Our present algorithm also incorporates an idea by which it can be checked whether or not an (m –2)-ary vector can be extended to a solution vector of m components, thereby backtracking is reduced by one component.     

An out-of-kilter based heuristic for the integer multicommodity transportation problem

A new formulation of the multicommodity transportation problem is introduced whereby all supply and demand constraints and in addition, a subset of the capacity constraints are incorporated into an equivalent single commodity, uncapacitated network. Solution of this network problem generally yields stronger lower bounds than one obtains by solving the individual single commodity transportation problems independently. A heuristic algorithm using this formulation is developed for the integer problem and limited computational experience indicates that the new formulation does provide a significant advantage over the unconstrained approach and solutions that are generally within seven percent of the lower bound. The application of this formulation in solving the continuous problem is also discussed.     

A set partitioning reformulation of a school bus scheduling problem

We present an integer programming model for the integrated optimization of bus schedules and school starting times, which is a single-depot vehicle scheduling problem with additional coupling constraints among the time windows. For instances with wide time windows the linear relaxation is weak and feasible solutions found by an ILP solver are of poor quality. We apply a set partitioning relaxation to compute better lower bounds and, in combination with a primal construction heuristic, also better primal feasible solutions. Integer programs with at most two non-zero coefficient per constraint play a prominent role in our approach. Computational results for several random and a real-world instance are given and compared with results from a standard branch-and-cut approach.