Extensions of the Petal Method for Vehicle Routeing

The petal method for vehicle routeing imposes special structure on the form of a feasible route. In this paper we show that by extending the definition of a petal route, more general forms of vehicle route can be generated without invalidating the important underlying property that optimal petal solutions can be produced very easily. It will also be shown that the optimal generalized petal solution can be produced efficiently by multiple applications of a shortest path algorithm.     

A Heuristic for Vehicle Routeing and Depot Staffing

This paper discusses the approach taken in solving a specific depot staffing and routeing problem. The problem differs from the normal routeing exercise in that the route passes through a number of outlets where monetary collections are made. Owing to the ever increasing risks of carrying money there is a requirement for the money to be deposited at banks along the route. Consequently, the more traditional routeing and scheduling methodologies and software are not easily applied to the problem. This paper details the approach used and highlights some of the good points and the pitfalls in the proposed solution.     

A Repeated Matching Heuristic for the Vehicle Routeing Problem

A new heuristic for the vehicle routeing problem which makes use of repeated matching is described. The numerical results are comparable to or better than the best published for most of the 14 benchmark problems commonly used to evaluate VRP heuristics.     

A Branch and Bound Algorithm for a Class of Asymmetrical Vehicle Routeing Problems

This paper describes a branch and bound algorithm for a general class of asymmetrical vehicle routeing problems. Vehicle routes start and end at a central depot. Visits are made to nodes grouped into clusters: every cluster must receive a minimum number of visits. But not all nodes must be visited: there are specified nodes and non-specified nodes. Vehicle routes are also constrained by capacity and distance restrictions. The problem is formulated as an integer linear program. It is then solved by a branch and bound algorithm which exploits the unimodular structure of the subproblems. Computational results are reported.     

Vehicle Routeing with Multiple Use of Vehicles

The vehicle routeing problem with multiple use of vehicles is a variant of the standard vehicle routeing problem in which the same vehicle may be assigned to several routes during a given planning period. A tabu search heuristic is developed for this problem. It is shown to produce high quality solutions on a series of test problems.     

An Interactive Algorithm for Vehicle Routeing for Winter — Gritting

In winter, when roads may become dangerously slippery due to frost, ice or snow, a de-icing agent (usually salt) is spread on them by a local authority for safety reasons. A gritter only needs to travel once down all those roads requiring treatment, as it can spread the salt onto both sides of the carriageway. The problem studied is how to design routes for gritters which will minimise costs. This problem is a type of Capacitated Arc Routeing Problem including consideration of multiple depot locations, limited vehicle capacities, time constraints on when roads must be gritted, roads with different priorities for gritting, the existence of one-way roads and salt-refilling locations. The objective function to be optimised depends on both the total distance travelled and the number and capacity of the gritters. A heuristic algorithm is devised with a computer program which allows user-interaction, and provides a practical tool for planning gritter routes. The model is linked to a GIS containing information on the road network for the County of Lancashire. Test results from the interactive algorithm are found to outperform another existing approach which solves the same problem.     

An Improved Petal Heuristic for the Vehicle Routeing Problem

Solutions produced by the first generation of heuristics for the vehicle routeing problem are often far from optimal. Recent adaptations of local search improvement heuristics, like tabu search, produce much better solutions but require increased computing time. However there are situations where good solutions must be obtained quickly. The algorithm proposed in this paper yields solutions almost as good as those produced by tabu search adaptations, but at only a small fraction of their computing time. This heuristic can be seen as an improved version of the original petal heuristic. On 14 benchmark test problems, the proposed heuristic yields solutions whose values lie on average within 2.38% of that of the best known solutions.     

Simple Heuristics for the Vehicle Routeing Problem with Soft Time Windows

We describe three simple heuristics for the vehicle routeing problem with customer time windows that can be violated by paying appropriate penalties. The customer demands are known, and a homogeneous fleet of vehicles stationed at a single depot is considered. The penalty payable to a customer is assumed to be a linear function of the amount of time window violation. Upper limits are imposed on both the penalty payable and the waiting time allowed at any customer. At each customer in a route, the PC-based heuristics simultaneously determine the actual time to begin service, and the next customer to serve. To achieve this, each heuristic uses different measures to compare the cost of waiting and penalty payable, with the benefit obtained by leaving immediately for the next customer. Computational results on a set of benchmark problems show that the procedure is efficient and enables significant reduction in the number of vehicles required and/or the total route distances while controlling both customer penalties and waiting times.     

Routeing in a Network with Multi-Class Links

Consider a communication network with certain nodes and different types of links. In addition to the normal link cost, a transformation cost is charged if the incoming link and the outgoing link are of different types. An optimal routeing from a given node to its destination node is sought. The major difficulty in handling this problem is that the principle of optimality does not hold. A model with node separation is built to overcome this difficulty. By using the new model, the original routeing problem is no more than a shortest-path problem. Hence, we can implement this model to current electronic switching machines.     

Routeing Road Sweepers in a Rural Area

A computer program has been developed to assist the routeing of road-sweeping vehicles in a part of the north-west of England. The aim of the study was to develop a method which would specify the route to be followed by each sweeper which minimized the dead distance travelled, subject to constraints on the capacity of the sweeper and the time available in any day. The method had to be flexible so that the effects of changes, such as new vehicles, alterations to the location of tips for detritus, or different frequencies of sweeping could be examined quickly. The paper describes how the design of the heuristic algorithm was influenced by the geography of the area, the computing facilities and the time available to complete the study.     

应急救援物资紧缺的配送车辆路径选择研究

针对应急救援物资总量紧缺不能全部满足各点需求量的实际情形,以单个需求点最大缺货量最小为目标,建立基于单个配送中心、车辆数目有限和带时间窗的应急救援物资配送车辆路径选择模型,并讨论了三种不同缺货情形下模型的求解。对于车辆按最短路径行驶也无法在救援时间内到达导致需求点缺货的情形,删除这些需求点的需求量后,如果剩余需求点的需求量不大于物资总量且车辆足够多,可转化为车辆最短路径问题求解;对于物资紧缺无法满足所有需求且车辆足够多的情形,设计时间复杂性为O(mn²)的精确算法A^*求解,其中m和n分别为车辆数和需求点数;对于物资紧缺且车辆数目不足无法把全部物资送达需求点的情形,设计时间复杂性为O(n²)的近似算法GA^*求解,并分析了算法GA^*的近似比。最后结合云南彝良县地震灾区局部路网进行实例分析,验证模型和算法的有效性。     

Combined Routeing and Scheduling for the Transportation of Containerized Cargo

A tractor-trailer problem, with full load, from the class of combined routeing and scheduling problems is described. Distinctive features of the problem are: movements must be carried out within certain time windows; subsets of movements are linked in the sense that they must be executed in a certain order; and different priorities are attached to different movements. A new bidirectional sequential constructive heuristic is developed for the solution of this problem. The method constructs routes and schedules for the available tractor fleet. The algorithm attempts to minimize the total time for all the movements by minimizing the time taken up by unproductive movements (so-called deadhead) and waiting time between movements. Some practical aspects of the implementation of the approach are discussed.     

The Impact of Risk Attitude on the Optimal Compensation Plan in a Multi-product Situation

This paper examines the role of uncertainty and risk in determining the optimal commission rates a company should choose for each product of a salesman's product line. We assume that sales for each product are a stochastic function of the time (sales effort) allocated to that product. When sales are assumed to be deterministic, we achieve optimality when each product's commission is the same fraction of its gross margin. However, we determine here that when sales are stochastic this may no longer be true. Optimality conditions require explicit consideration of the utility function of the salesman and the moments of the sales response function.     

随机产出环境下联产品的产量及价格策略研究

基于制造商生产主产品的过程中会随机产出两类存在替代关系的副产品的联产品系统,采用清仓定价模型,研究了不同需求函数(线性需求和指数需求)下,制造商对于主产品和副产品的最优产量与定价策略。通过两阶段优化模型的建立和求解,确定了主产品的最优产量和价格。借助数值分析,归纳出产品替代度和产出波动性对最优产量和利润的影响。研究结果表明,随着产品替代度的增加,制造商的产量上升;随着波动性的增加,制造商的产量下降。最后,将模型扩展到市场非出清的情况,并得出制造商的最优生产决策。     

A Clustering and Insertion Heuristic Applied to a Large Routeing Problem in Food Distribution

This article investigates a large food distributor and describes a heuristic approach to provide satisfactory solutions to large, realistic, complicated routeing problems of food distribution. The approach includes routeing (clustering and insertion) procedures and the allocation of drivers and vehicles. These procedures were heuristically developed, on the basis of the delivery data of three days of four large geographic regions. The approach was used to develop an integrated, interactive, computer-based system for routeing of food-service delivery vehicles after being tested on the problems of four to five days of seven geographic regions which cover the Western, Midwest and Southern United States. The sizes of the problems ranged from 5 to 24 routes per region and 69 to 308 customers per schedule. The revised approach improved the solutions of the previous system by an average of 5.6% of delivery costs. The cost savings were caused mainly by a reduction in the number of routes.     

Empirical Modeling of a Hydraulic Actuator in a Vehicle Control System

The pressure information of a hydraulic actuator plays a key role in modern vehicle control and fault diagnosis. The difficulty in measuring pressure directly naturally motivates such an indirect approach as an observer whose accuracy depends heavily upon the availability of a high fidelity model of a hydraulic actuator. Notwithstanding its success in understanding the dynamics of the first principle model of a hydraulic actuator, it is not suited to controller/observer design due to its complexity. This paper presents an alternative to the first principle modeling methodology: an empirical approach to hydraulic actuator modeling. Linear and nonlinear system identification techniques are applied to obtain low-order models of a hydraulic actuator. Experimental results show how the empirical models reproduce the key features of a hydraulic actuator with sufficient accuracy.     

供应链视角下的增值税改革影响研究

构建了一个制造商和一个零售商所组成的两级供应链模型,研究增值税税率下调对供应链决策和社会福利的影响.结果表明,下调制造商、零售商增值税税率都会使产品零售价降低,提高零售商和制造商的利润.下调增值税税率给制造商带来的利润增量大于给零售商带来的利润增量.制造商税率下调导致批发价降低,零售商税率下调反而提高批发价.社会福利的...     

一类具有优化调整状态的供应链系统的稳定性分析

主要研究一类具有优化调整状态的供应链系统解的适定性问题,利用C_0-半群理论和谱分析的方法,得到了此系统存在惟一的时间依赖解,并且当时间趋于无穷时,该时间依赖解收敛于其稳态解,而其稳态解恰好是系统算子的0本征值对应的本征向量.     

多环节供求系统模型

本文提出了多环节供求关系的数学模型,并胜计算机模拟计算的方法分析了造成供求关系严重失衡的原因,进而提出了防止产量大幅波的厂商生产动态决策模型。     

某型工程车系统可靠性分析

本应用失效树分析法,以某型工程车进行了可靠性分析,建立了该系统的失效树,在此基础上用最小割集法和系统失效树的可靠性仿真法计算了该系统的可靠性参数,并对一些结果进行了比较。