An exact solution for vehicle routing problems with semi-hard resource constraints

This paper presents an exact solution procedure for a vehicle routing problem with semi-hard resource constraints where each resource requirement can be relaxed to a pre-fixed extent at a predefined cost. This model is particularly useful for a supply chain coordination when a given number of vehicles cannot feasibly serve all the customers without relaxing some constraints.It is different from VRP with soft time windows in that the violation is restricted to a certain upper bound, the penalty cost is flat, and the number of relaxations allowed has an upper bound.We develop an exact approach to solve the problem. We use the branch cut and price procedure to solve the problem modeling the pricing problem as an elementary shortest path problem with semi hard resource constraints. The modeling of the subproblem provides a tight lower bound to reduce the computation time. We solve this subproblem using a label setting algorithm, in which we form the labels in a compact way to facilitate incorporation of the resources requirement relaxation information into it, develop extension rules that generate labels with possible relaxations, and develop dominance criteria that reduce the computation time. The lower bound is improved by applying the subset-row inequalities.     

基于约束传播的HFS调度研究

将约束传播技术同分枝定界法相结合求解优化目标为最小最大完工时间的混合流水车间调度问题。算法核心是根据资源松弛度确定关键阶段,通过在分枝定界算法中嵌入动态可调的开工时间窗口,用顺序传播、资源传播、上下游工序传播,动态修改每个操作的开工时间窗上下界,并在算法特点基础上给出相应的剪枝下界,以减小搜索空间,提高分枝定界法的优化能力。实验结果证明了算法的有效性。     

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.     

多跳无线网络中基于分支限界法的广播算法

现有的广播算法一般采用分层的方法构建近似的最多叶子最短生成树作为广播树。分析此类算法存在的不足,提出利用分支限界的思想建立最多叶子最短生成树引导广播操作的方法。分析和仿真结果表明,与基于分层的广播算法相比,基于分支限界法的广播算法具有更低的转发比且不增加广播树的深度,能更有效地节省带宽和能量资源。     

The green vehicle routing problem: A heuristic based exact solution approach

This paper develops a simulated annealing heuristic based exact solution approach to solve the green vehicle routing problem (G-VRP) which extends the classical vehicle routing problem by considering a limited driving range of vehicles in conjunction with limited refueling infrastructure. The problem particularly arises for companies and agencies that employ a fleet of alternative energy powered vehicles on transportation systems for urban areas or for goods distribution. Exact algorithm is based on the branch-and-cut algorithm which combines several valid inequalities derived from the literature to improve lower bounds and introduces a heuristic algorithm based on simulated annealing to obtain upper bounds. Solution approach is evaluated in terms of the number of test instances solved to optimality, bound quality and computation time to reach the best solution of the various test problems. Computational results show that 22 of 40 instances with 20 customers can be solved optimally within reasonable computation time.     

多车场多车型车辆路径问题的改进遗传算法

在给出有时间窗约束的多车场多车型车辆路径问题的基于直观描述的数学模型基础上,引入一种新的编码方式,并将RC交叉算子进行修正,构造出一种解决该问题的模拟退火遗传算法,实验证明能够有效地解决优化问题。     

A branch-and-bound algorithm for single machine scheduling with quadratic earliness and tardiness penalties

This paper considers the problem of scheduling a single machine, in which the objective function is to minimize the weighted quadratic earliness and tardiness penalties and no machine idle time is allowed. We develop a branch and bound algorithm involving the implementation of lower and upper bounding procedures as well as some dominance rules. The lower bound is designed based on a lagrangian relaxation method and the upper bound includes two phases, one for constructing initial schedules and the other for improving them. Computational experiments on a set of randomly generated instances show that one of the proposed heuristics, used as an upper bound, has an average gap less than 1.3% for instances optimally solved. The results indicate that both the lower and upper bounds are very tight and the branch-and-bound algorithm is the first algorithm that is able to optimally solve problems with up to 30 jobs in a reasonable amount of time.     

基于改进分支定价法的车辆路径优化研究

为克服分支定价算法中基于{0,1}的分支策略在求解车辆路径问题时效率和稳定性方面的缺陷,提出了一种双重禁用的分支策略。该分支策略在分支阶段首先通过筛选一组出弧数量最多的集合,然后按照一定的规则将其分为两组,左右分支分别对包含这两组弧的路线进行禁用,禁用的范围不仅局限于分支阶段,在之后的定价阶段同样需要禁止该弧的使用。双重禁用的分支策略不仅实现了分支定界树所需的分支功能,而且达到了求解效率和质量的平衡。通过采用包含强时间窗约束、载重约束、里程约束的车辆路径问题相关的算例,验证了相对于基于{0,1}的分支策略具有较强的寻优和稳定性能。     

The multiple disposal facilities and multiple inventory locations rollon–rolloff vehicle routing problem

In the Multiple disposal facilities and multiple inventory locations rollon–rolloff vehicle routing problem (M-RRVRP), one of the very important pickup and disposal problems in the sanitation industry, tractors move large trailers, one at a time, between customer locations such as construction sites and shopping centers, disposal facilities and inventory locations. In this paper, we model the M-RRVRP as a time constrained vehicle routing problem on a multigraph (TVRP-MG). We then formulate the TVRP-MG as a set partitioning problem with an additional constraint and describe an exact method for solving the TVRP-MG. This exact method is based on a bounding procedure that combines three lower bounds derived from different relaxations of the formulation of the problem. Further, we obtain a valid upper bound and show how this bounding procedure can transform the solution of a Lagrangean lower bound into a feasible solution.     

A Novel Model for the Time Dependent Competitive Vehicle Routing Problem: Modified Random Topology Particle Swarm Optimization

This paper presents a novel model for a time dependent vehicle routing problem when there is a competition between distribution companies for obtaining more sales. In a real-world situation many factors cause the time dependency of travel times, for example traffic condition on peak hours plays an essential role in outcomes of the planned schedule in urban areas. This problem is named as “Time dependent competitive vehicle routing problem” (TDVRPC) which a model is presented to satisfy the “non-passing” property. The main objectives are to minimize the travel cost and maximize the sale in order to serve customers before other rival distributors. To solve the problem, a Modified Random Topology Particle Swarm Optimization algorithm (RT-PSO) is proposed and the results are compared with branch and bound algorithm in small size problems. In large scales, comparison is done with original PSO. The results show the capability of the proposed RT-PSO method for handling this problem.     

航天测控调度分枝定界算法

通过分析航天测控调度问题的测控需求,建立了航天测控调度整数规划模型,引入了拉格朗日松弛思想并与分枝定界算法结合,设计了基于拉格朗日松弛的分枝定界算法求解航天测控调度问题。通过对两个场景的仿真实验,得到了两个场景的航天测控调度问题最优值,验证了基于拉格朗日松弛的分枝定界算法的有效性。     

The reduced cost branch and bound algorithm for mixed integer programming

A different branch and bound algorithm for mixed integer programming is presented. Unlike standard linear programming based branch and bound algorithms, where a single fractional variable (or Special Ordered Set) is selected for problem separation, the proposed method selects groups of variables for separation on the basis of their reduced cost in an LP relaxation. The proposed method restricts a large portion of the integer variables to zero on one branch. The net effect is that the original integer program is solved by optimizing a series of smaller, more tightly restricted, integer programs. The authors have programmed the algorithm using the Extended Control Language of the IBM MPSX/370-MIP/370 mixed integer programming package. Computational results are presented that demonstrate the efficiency of the method on problems where the $\text{0}\text{1}$ variables are partitioned into multiple choice constraints containing special ordered sets of variables. While the computational results are limited to this class of problems the algorithm can, in theory, be applied to any mixed integer programming problem.     

Controlling left and u-turns in the routing of refuse collection vehicles

In this paper, a well-known algorithm for the one-vehicle directed branch routing problem is reviewed. The parts of the algorithm which permit left and u-turns to be created are analyzed. Left and u-turns are generally undesirable in refuse collection vehicle routes, because they may be dangerous and/or time consuming. Techniques which can be used to reduce the number of left and u-turns are presented.     

A branch-and-price-and-check model for the vehicle routing problem with location congestion

This paper considers a vehicle routing problem with pickup and delivery, time windows and location congestion. Locations provide a number of cumulative resources that are utilized by vehicles either during service (e.g., forklifts) or for the entirety of their visit (e.g., parking bays). Locations can become congested if insufficient resources are available, upon which vehicles must wait until a resource becomes available before proceeding. The problem is challenging from a computational standpoint since it incorporates the vehicle routing problem and the resource-constrained project scheduling problem. The main contribution of this paper is a branch-and-price-and-check model that uses a branch-and-price algorithm that solves the underlying vehicle routing problem, and a constraint programming subproblem that checks the feasibility of the location resource constraints, and then adds combinatorial nogood cuts to the master problem if the resource constraints are violated. Experimental results show the benefits of the branch-and-price-and-check approach.     

三阶段拉格朗日启发式算法求解带同时取送货的绿色车辆路径问题

针对带同时取送货的绿色车辆路径问题,以最小化带碳排放费用的配送成本为优化目标,建立混合整数规划模型,并提出一种结合数学规划方法与启发式算法的三阶段拉格朗日启发式算法进行求解.第1阶段,利用拉格朗日松弛技术得到该问题的拉格朗日对偶模型;第2阶段,设计一种改进的次梯度算法迭代求解该对偶模型,同时引入修复机制,将每次迭代所得下界对应的解修复为原问题较高质量的可行解,并在下次迭代中利用该可行解更新次梯度方向和步长;第3阶段,设计一种启发式局部搜索算法,对第2阶段得到的可行解进行优化,进一步改进解的质量,以得到原问题的近似最优解.实验表明,所提出算法能够获得问题的一个优质解,同时提供一个紧致下界,用以定量评估解的质量.     

基于混合算法的带时间窗的车辆路径问题求解

建立了有时间窗车辆路径问题的数学模型,针对遗传算法在局部搜索能力方面的不足,提出将模拟退火算法与遗传算法相结合,从而构造了有时间窗车辆路径问题的混合遗传算法,并进行了实验计算。结果表明,用混合遗传算法求解该优化问题,可以在一定程度上克服遗传算法在局部搜索能力方面的不足和模拟退火算法在全局搜索能力方面的不足,从而得到了质量较高的解。     

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

带时间窗和容量约束的车辆路径问题是车辆路径问题重要的扩展之一,属于NP难题,精确算法的求解效率较低,且对于较大规模问题难以在有限时间内给出最优解.为了满足企业和客户快速有效的配送需求,使用智能优化算法可以在有限的时间内给出相对较优解.研究了求解带容量和时间窗约束车辆路径问题的改进离散蝙蝠算法,为增加扰动机制,提高搜索速度和精度,在对客户点按其所在位置进行聚类的基础上,在算法中引入了变步长搜索策略和两元素优化方法进行局部搜索.仿真实验结果表明,所设计算法具有较高寻优能力和较强的实用价值.     

Solving school bus routing using the multiple vehicle traveling purchaser problem: A branch-and-cut approach

School bus routing problems, combining bus stop selection and bus route generation, look simultaneously for a set of bus stops to pick up students from among a group of potential locations, and for bus routes to visit the selected stops and carry the students to their school. These problems, classified as Location-Routing problems, are of interest in densely populated urban areas.This article introduces a generalization of the vehicle routing problem called the multi-vehicle traveling purchaser problem, modeling a family of routing problems combining stop selection and bus route generation. It discusses a Mixed Integer Programming formulation extending previous studies on the classical single vehicle traveling purchaser problem. The proposed model is based on a single commodity flow formulation combining continuous variables with binary variables by means of coupling constraints. Additional valid inequalities are proposed with the purpose of strengthening its Linear Programming relaxation. These valid inequalities are obtained by projecting out the flow variables.We develop a branch-and-cut algorithm that makes use of the proposed model and valid inequalities. This cutting plane algorithm is implemented and tested on a large family of symmetric and asymmetric instances derived from randomly generated problems, showing the usefulness of the proposed valid inequalities.     

A hybrid genetic algorithm for multi-depot homogenous locomotive assignment with time windows

This paper presents a hybrid genetic algorithm to solve a multi-depot homogenous locomotive assignment problem with time windows. The locomotive assignment problem is to assign a set of homogeneous locomotives locating in a set of dispersed depots to a set of pre-schedules trains that are supposed to be serviced in pre-specified hard/soft time windows. A mathematical model is presented, using vehicle routing problem with time windows (VRPTW) for formulation of the problem. A cluster-first, route-second approach is used to inform the multi-depot locomotive assignment to a set of single depot problems and after that we solve each problem independently. Each single depot problem is solved heuristically by a hybrid genetic algorithm that in which Push Forward Insertion Heuristic (PFIH) is used to determine the initial solution and λ-interchange mechanism is used for neighborhood search and improving method. A medium sized numerical example with different scenarios is presented and examined to more clarification of the approach as well as to check capabilities of the model and algorithm. Also some of the results are compared with the solutions produced by branch & bound technique to determine validity and quality of the model. The experiments with a set of 15 completely random generated instance problems indicate that this algorithm is efficient and solves the problem in a polynomial time.     

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.