Scheduling Vehicles for Refuse Collection

This paper reports an application of vehicle-scheduling algorithms in the collection of refuse. The problem differs from classical vehicle-scheduling applications in that the tipping site and the place where the vehicles are garaged are at different locations. Several algorithms are tested in terms of total route mileage and computational loads. An improvement over the manual method of the order of 8% was obtained using average figures for refuse volume over a period of time. The results appear to be more useful in obtaining a good solution when the main problem parameters change rather than in the day-to-day routeing of vehicles.     

An Algorithmic Framework for Routeing LTL Shipments

One way of reducing the unit cost of shipment by a motor carrier is to consolidate many LTL (less-than-truck-load) shipments. Explicit information on the route structure is a prerequisite to the understanding of the costs of the services provided and to the planning of the allocation of the equipment and personnel among the terminals. In this paper, an approach for routeing the LTL shipments is presented and is applied to a hypothetical network. Solution results of this example show that the algorithm offers an efficient and reasonably accurate method for the routeing of LTL shipments via the intermediate terminals.     

Solving the AGV Problem via a Self-Organizing Neural Network

Automated Guided Vehicle (AGV)-based material handling systems (MHS) are used widely in Flexible Manufacturing Systems (FMS). The problem of AGV consists of the decisions and the operational control strategies of dispatching, routeing and scheduling of a set of AGVs under given system environments and operational objectives. One remaining challenge is to develop effective methods of AGV decisions for improved system productivity. This paper describes a prototype neural network approach for the AGV problem in an FMS environment. A group of neural network models are proposed to perform dispatching and routeing tasks for the AGV under conditions of single or multiple vehicles, and with or without time windows. The goal is to satisfy the transport requests in the shortest time and in a non-conflicting manner, subject to the global manufacturing objectives. Based on Kohonen's self-organizing feature maps, we have developed efficient algorithms for the AGVs decisions, and simulation results have been very encouraging.     

Interactive Vehicle Routeing

No single approach to vehicle routeing has either the sophistication or the flexibility needed to tackle many real problems. Interactive routeing which emphasizes the experience of human schedulers may prove helpful. The main requirement would be that computers assist rather than replace humans. Use of one interactive package is described and a comparison with automatically produced results is given for test problems. Application of the approach to a real problem is outlined.     

Practical Vehicle Routeing Using Computer Programs

This article gives an account of a trial by a large company of VANPLAN, Scicon Consultancy's Vehicle routeing computer package.It covers the various logical stages in the trial of project design, data collection and validation, staff training and acceptance criteria.The article also highlights the advantages of using computers interactively to plan routes using the skills of existing staff. This is compared with the ‘traditional’ operational research approach using automatic routeing algorithms. Suggestions are also made regarding how to properly and fully test new routeing algorithms or techniques.     

Interdependent Transportation and Production Activity at the United States Postal Service

Transportation decisions and production decisions can usually be made separately. Under certain conditions, however, there are important interactions between transportation and production. An example of a combined production and routeing environment exists in the United States Postal Service (USPS). The daily movement and sorting of first class letter mail requires balancing transportation and mail sorting production costs, while considering the time dependent accumulation of mail during the day. The focus of this paper is on the practical application of a combined production/routeing model to a specific USPS division and the use of insights from this model to re-design the operation. A mixed integer linear program using candidate route integer variables is solved to near optimality. Specific routes and production schedules detailed by the model indicate that the division could save up to 5% of their combined production and routeing costs, amounting to $298 000 per year. More importantly, the model provides insight on potential heuristics to choose routes under these circumstances.     

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 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.     

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.     

Solving the open vehicle routeing problem via a single parameter metaheuristic algorithm

In this paper, we consider the open vehicle routeing problem (OVRP), in which routes are not sequences of locations starting and ending at the depot but open paths. The problem is of particular importance for planning fleets of hired vehicles, a common practice in the distribution and service industry. In such cases, the travelling cost is a function of the vehicle open paths. To solve the problem, we employ a single-parameter metaheuristic method that exploits a list of threshold values to guide intelligently an advanced local search. Computational results on a set of benchmark problems show that the proposed method consistently outperforms previous approaches for the OVRP. A real-world example demonstrates the applicability of the method in practice, demonstrating that the approach can be used to solve actual problems of routing large vehicle fleets.     

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.     

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.     

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.     

An Air Force Crew Allocation and Scheduling Problem

This paper considers an airline crew allocation and scheduling problem faced by certain divisions of the United States Air Force. Two variants of the problem under consideration were posed to us by the U.S. Air Force. This paper reports our experience with two heuristic methods developed, each applicable to either variant of the problem. Although the problem described herein is peculiar to this situation, the heuristic scheduling and dispatching rules developed have been found to be very effective and are generally applicable in other related contexts of routeing and crew and vehicle scheduling problems as well. The two algorithms developed have been applied to a coded set of real world data. The results indicate that each one of the two methods is preferable to the other for one of the two variants of the problem. This suggests an overall effective composite technique.     

Decomposing Timed Petri Net Models of Open Queueing Networks

This paper develops a Petri net-based decomposition approach to model and perform steady-state analysis of open queueing networks with multi-class customers. For each customer class we assume deterministic routeing and different service time distribution. The current decomposition may also consider equipment failures, defective units that have to be re-worked and on-line preparations (to switch from one mix of customers to another) as additional customer classes. In contrast to most of the published works on timed Petri nets, their present use is marked by input flows, originating from external sources. A simple method, directly derived from the timed Petri nets theories, is used for calculating the expected utilization of each server and eventually the maximal productivity of the system for the given deterministic routeing. An important application of the model is in validating discrete-event non-terminating simulation models.     

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.     

An Exchange Heuristic for Routeing Problems with Time Windows

In this paper, we compare different exchange heuristics for vehicle routeing problems with time windows. We also introduce a new 2-opt* exchange heuristic, and show that a hybrid approach, based on Or-opt and 2-opt* exchanges, is particularly powerful for problems with time windows. Computational results are reported for randomly generated problems and for a standard test set.     

Generalized Subtour Elimination Constraints and Connectivity Constraints

This paper examines some properties of generalized subtour elimination constraints and connectivity constraints used in a variety of routeing problems.     

The Impact of a Decision-Support System for Vehicle Routeing in a Foodservice Supply Situation

Efficient vehicle routeing is critical to the competitive position of firms in many industries. The foodservice industry encounters complex and constantly changing routeing problems in which time is a critical factor. With the cooperation and support of management and staff of Kraft Inc., we implemented an heuristic-based decision-support system, which utilizes computer-graphic pictures of routes in a large foodservice distribution region of Kraft Inc.The system provides the route scheduler with a tool to enable the rapid evaluation of computer-proposed solutions and to easily modify them. In tests conducted by Kraft personnel, system users found potential variable cost savings of 10.7% on 10 actual delivery problems of up to 223 stops. A potential for reductions in fixed costs was also indicated. The system allows the scheduler great flexibility in dealing with unpredictable factors and also aids management in strategic planning for distribution. It is currently in day-to-day use at Kraft.