校车站点及线路的优化设计

以高校新校区教师校车站点及线路安排为对象,首先针对乘车站点建立了双目标非线性规划模型,其中目标函数包括乘客到达站点的距离偏差最小与所有乘客到达站点的总的距离最小两个方面;站点确定后针对车辆数最少、车辆行驶的总距离最短、各辆车的运行距离均衡及各辆车的负荷均衡这4个目标建立针对线路优化的多目标非线性规划模型,并给出了解决这类问题的启发式优化算法.与目前国内外研究相比较,该模型与算法更实际,更具体的给出了问题的解答.     

Effect of Modeling Uncertainty on Some Routing Problems

In this paper, we consider the routing problem described in Mohanty and Cassandras (Ref. 1). As in Ref. 1, we show that the optimal Bernoulli split to minimize mean time in the system is asymptotically independent of the variance of the service time. We give simple proofs of the results in that paper. We exploit the fact that the optimal split to minimize the mean queueing time is variance independent and the special structure of the Karush–Kuhn–Tucker optimality conditions to derive the optimal solution. Apart from being very straightforward, the proofs also give insight into the reason for the existence of the variance-independent asymptotically optimal routing policy.     

Bakhvalov-Shishkin网格上求解边界层问题的差分进化算法

该文在Bakhvalov-Shishkin网格上求解具有左边界层或右边界层的对流扩散方程,并采用差分进化算法对Bakhvalov-Shishkin网格中的参数进行优化,获得了该网格上具有最优精度的数值解.对三个算例进行了数值模拟,数值结果表明:采用差分进化算法求解具有较高的计算精度和收敛性,特别是边界层的数值解精度明显...     

公交车动态调度模型研究

本文通过对照车辆行车时刻表与实际运行到达各站的偏差 ,建立动态调度模型 ,对车辆实施动态调度 ,以保证线路的行车间隔和车辆载客量均匀 ,提高公交服务质量     

Mesh Selection in Collocation for Boundary Value Problems

This paper introduces some subdivision criterion functions foruse in adaptive algorithms for the solution of linear ordinarydifferential equations by piecewise polynomial collocation methods.These criterion functions aim to take into account the influenceof the behaviour in one subinterval on the error in others.They are compared with various alternatives using examples whichinclude problems with interior or boundary layers. These examplesillustrate some of the difficulties which can arise. The dangerof using criterion functions based on estimates of the globalerror is emphasized.     

Competitive Memetic Algorithms for Arc Routing Problems

The Capacitated Arc Routing Problem or CARP arises in applications like waste collection or winter gritting. Metaheuristics are tools of choice for solving large instances of this NP-hard problem. The paper presents basic components that can be combined into powerful memetic algorithms (MAs) for solving an extended version of the CARP (ECARP). The best resulting MA outperforms all known heuristics on three sets of benchmark files containing in total 81 instances with up to 140 nodes and 190 edges. In particular, one open instance is broken by reaching a tight lower bound designed by Belenguer and Benavent, 26 best-known solutions are improved, and all other best-known solutions are retrieved.     

Heuristics for Large Constrained Vehicle Routing Problems

This paper presents a heuristic for solving very large routing problems (thousands of customers and hundreds of vehicles) with side constraints such as time windows. When applied to traditional benchmarks (Solomon's), we obtain high quality results with short resolution time (a few seconds). We also introduce a LDS (Limited Discrepancy Search) variation that produces state-of-the-art results. The heart of this heuristic is a combination of a look-ahead insertion algorithm, an incremental local optimization scheme and a constraint solver for constrained traveling salesman problems. The incrementality means that instead of visiting some large neighborhood after an initial solution has been found, a limited number of moves is examined, after each insertion, on the partial solution. This incremental version is not only faster, it also yields better results than using local optimization once a full solution has been built. We also show how additional constraints can be used in order to guide the insertion process. Because of its use of separate CP (Constraint Programming) modules, this method is flexible and may be used to solve large dispatching problems that include many additional constraints such as setup times (asymmetrical distance) or skill matching.     

公交车调度的数学模型

通过建模求解了2001年大学生数学建模竞赛B题,文中根据在最大程度上照顾乘客和公司双方的利益及调度方便的要求把该问题归结为多目标决策问题,利用逐段最优算法求出最优调度方案,并求得了发车时刻表及所需最少车辆数.     

Hybrid Voronoi Mesh Generation: Algorithms and Unsolved Problems

Computational Mathematics and Mathematical Physics - We consider problem of constructing Voronoi mesh where the union of Voronoi cells approximates the computational domain with a piecewise smooth...     

基于遗传算法的物流配送车辆调度问题研究

研究使用遗传算法求解物流配送组织过程中车辆调度问题 .通过把时间窗约束和车辆容量约束转嫁到最小费用目标函数中去 ,建立适合于遗传算法的车辆调度模型 .阐述放回式随机复制算子和适应度函数 ,设计描述行驶线路的染色体结构、初始群体生成方法、独特的交叉算子和交换变异算子 ,构造完整的遗传算法 .并给出算例 ,验证调度模型和遗传算法 .     

校车安排问题

探讨如何安排校车运行使得教师和工作人员尽量满意的问题.首先建立动态规划模型和选址规划模型,求出合理站点位置及其总距离.然后用归一法定义满意度与距离的函数关系,考虑各区域人数,建立选址规划模型.得到合理站点位置和总满意度.之后建立双目标非线性规划模型,利用量纲分析法给出权重,以此求出合理乘车位置和满意度.最后对问题进行推...     

车辆路径问题的混合优化算法

讨论了一类车辆路径调度问题(VRP)及其数学模型，并且分析了以遗传算法求解该类问题时的染色体表示和有关遗传操作，然后结合2-opt局部优化算法提出了GA with2-opt算法来求解VRP问题，试验结果说明了该算法的有效性和可行性。     

A Hybrid Mesh Selection Strategy Based on Conditioning for Boundary Value ODE Problems

An appropriate mesh selection strategy is one of the fundamental tools in designing robust codes for differential problems, especially if the codes are required to work for difficult multi scale problems. Most of the existing codes base the mesh selection on an estimate of the error (or the residual). Our strategy, based on the estimation of two parameters characterising the conditioning of the continuous problem, as well as on an estimate of the error, not only permits us to obtain a well adapted mesh, thus reducing the cost of the code, but also provides a measure of the conditioning of both continuous and discrete problems.     

随机需求的车辆路线问题的新模型

本主要研究随机需求的VRP问题,其中服务需求量满足二项式分布,根据期望值的大小我们提出了在一条路线上理想最大服务点数的新概念,并在此基础上建立了三种VRP问题的新模型,由于允许服务失败两次和部分服务使得模糊能适应多种实际问题,以模拟退火思想为基础的两阶段方法经修正后用于解新模型并取得较好的数值结果,理论分析和数值结果表明,新模型较好地描述随机需求的VRP问题,并且容易求解。     

部分联合运输策略下的物流车辆路径优化问题研究

论文分析了物流车辆路径优化问题的特点,提出了企业自营物流和第三方物流协同运输的部分联合运输策略。根据客户需求节点的特点进行了节点分类,建立了以车辆调用成本、车辆运输成本、第三方物流运输成本之和最小为目标的整数线性规划模型。根据部分联合运输策略下各类客户需求点运输方式特点,构造了一种新的变维数矩阵编码结构,并对传统算法中概率选择操作方式进行修改,提出了一种新的智能优化算法并与枚举法和遗传算法的运算结果进行了算法性能对比分析。结果显示,本文提出的逆选择操作蚁群算法具有较快的运算速度和较高的稳定性,是求解此类问题的一种有效算法。     

A new ILP-based refinement heuristic for Vehicle Routing Problems

In this paper we address the Distance-Constrained Capacitated Vehicle Routing Problem (DCVRP), where k minimum-cost routes through a central depot have to be constructed so as to cover all customers while satisfying, for each route, both a capacity and a total-distance-travelled limit. Our starting point is the following refinement procedure proposed in 1981 by Sarvanov and Doroshko for the pure Travelling Salesman Problem (TSP): given a starting tour, (a) remove all the nodes in even position, thus leaving an equal number of ``empty holes' in the tour; (b) optimally re-assign the removed nodes to the empty holes through the efficient solution of a min-sum assignment (weighted bipartite matching) problem. We first extend the Sarvanov-Doroshko method to DCVRP, and then generalize it. Our generalization involves a procedure to generate a large number of new sequences through the extracted nodes, as well as a more sophisticated ILP model for the reallocation of some of these sequences. An important feature of our method is that it does not rely on any specialized ILP code, as any general-purpose ILP solver can be used to solve the reallocation model. We report computational results on a large set of capacitated VRP instances from the literature (with symmetric/asymmetric costs and with/without distance constraints), along with an analysis of the performance of the new method and of its features. Interestingly, in 13 cases the new method was able to improve the best-know solution available from the literature. Work supported by M.I.U.R. and by C.N.R., Italy.     

Solving Vehicle Routing Problems Using Constraint Programming and Metaheuristics

Constraint Programming typically uses the technique of depth-first branch and bound as the method of solving optimization problems. Although this method can give the optimal solution, for large problems, the time needed to find the optimal can be prohibitive. This paper introduces a method for using local search techniques within a Constraint Programming framework, and applies this technique to vehicle routing problems. We introduce a Constraint Programming model for vehicle routing, and a system for integrating Constraint Programming and local search techniques. We then describe how the method can be accelerated by handling core constraints using fast local checks, while other more complex constraints are left to the constraint propagation system. We have coupled our local search method with a meta-heuristic to avoid the search being trapped in local minima. Several meta-heuristics are investigated ranging from a simple Tabu Search method to Guided Local Search. An empirical study over benchmark problems shows the relative merits of these techniques. Investigations indicate that the specific long-term memory technique used by Guided Local Search can be used as a diversification method for Tabu Search, resulting in significant benefit. Several new best solutions on the Solomon problems are found in relatively few iterations of our algorithm.     

Parallelization of a Two-Phase Metaheuristic for Routing Problems with Time Windows

This paper describes the parallelization of a two-phase metaheuristic for the vehicle routing problem with time windows and a central depot (VRPTW). The underlying objective function combines the minimization of the number of vehicles in the first search phase of the metaheuristic with the minimization of the total travel distance in the second search phase. The parallelization of the metaheuristic follows a type 3 parallelization strategy (cf. Crainic and Toulouse (2001). In F. Glover and G. Kochenberger (eds.). State-of-the-Art Handbook in Metaheuristics. Norwell, MA: Kluwer Academic Publishers), i.e. several concurrent searches of the solution space are carried out with a differently configured metaheuristic. The concurrently executed processes cooperate through the exchange of solutions. The parallelized two-phase metaheuristic was subjected to a comparative test on the basis of 358 problems from the literature with sizes varying from 100 to 1000 customers. The derived results seem to justify the proposed parallelization concept.     

A Queueing Framework for Routing Problems with Time-dependent Travel Times

Assigning and scheduling vehicle routes in a dynamic environment is a crucial management problem. Despite numerous publications dealing with efficient scheduling methods for vehicle routing, very few addressed the inherent stochastic and dynamic nature of travel times. In this paper, a vehicle routing problem with time-dependent travel times due to potential traffic congestion is considered. The approach developed introduces the traffic congestion component based on queueing theory. This is an innovative modelling scheme to capture the stochastic behavior of travel times as it generates an analytical expression for the expected travel times as well as for the variance of the travel times. Routing solutions that perform well in the face of the extra complications due to congestion are developed. These more realistic solutions have the potential to reduce real operating costs for a broad range of industries which daily face routing problems. A number of datasets are used to illustrate the appropriateness of the novel approach. Moreover it is shown that static (or time-independent) solutions are often infeasible within a congested traffic environment which is generally the case on European road networks. Finally, the effect of travel time variability (obtained via the queueing approach) is quantified for the different datasets.