The downhill plow problem with multiple plows

In winter, a common problem is to determine a set of routes for snow plows that minimize the maximum route length. Typically, this is modelled as an arc routing problem. We begin with a variant that is motivated by the fact that deadhead travel over streets is significantly faster than the time it takes to plow the street. We incorporate the use of multiple plows and the observation that, on steep streets, it is much more difficult, or impossible, to plow uphill. Therefore, we want to design routes that try to avoid plowing uphill on steep streets and take advantage of the faster traversal time for deadheading. We generalize this problem to include multiple plows and seek to minimize the maximum route length. We present a heuristic that generates solutions with costs that are very close to a lower bound.     

Solving the minimum toll revenue problem in real transportation networks

As a means to relieve traffic congestion, toll pricing has recently received significant attention by transportation planners. Inappropriate use of transportation networks is one of the major causes of network congestion. Toll pricing is a method of traffic management in which traffic flow is guided to proper time and path in order to reduce the total delay in the network. This article investigates a method for solving the minimum toll revenue problem in real and large-scale transportation networks. The objective of this problem is to find link tolls that simultaneously cause users to efficiently use the transportation network and to minimize the total toll revenues to be collected. Although this model is linear, excessive number of variables and constraints make it very difficult to solve for large-scale networks. In this paper, a path-generation algorithm is proposed for solving the model. Implementation of this algorithm for different networks indicates that this method can achieve the optimal solution after a few iterations and a proper CPU time.     

A common notion of clockwise can help in planar rendezvous

Two players are lost in a grid of city streets and wish to meet as soon as possible. Knowing only the distribution of the other’s initial location (two nodes away in one of the four compass directions), how do they move from intersection to intersection (between nodes of the lattice Z²) to achieve this? We assume that they do not have common compass directions to coordinate on, but that they can use their common notion of clockwise. We show that the latter, realistic assumption, can aid them in expediting their meeting (relative to a previous rendezvous problem which did not allow this). We also solve the easier ‘streets and avenues’ version of the problem, in which the players can distinguish between the axes (between streets and avenues). We discover several new phenomena which have not been seen before in planar rendezvous.     

A computational study of several heuristics for the DRPP

The problem of designing a route of minimum length for a postman that starts and finishes at his office and has to deliver the mail along a set of streets in a city is known as the Rural Postman Problem. When the postman has to obey the directions of the streets, we have the directed version of this problem. Finding an exact solution, in the general case, is intractably difficult. Hence, we have implemented three heuristic algorithms for approximately solving this problem and a procedure for obtaining a lower bound to the optimal length. Also, we present numerical experimentations based on a collection of random instances with up to 30 connected components, 240 vertices and 801 arcs. A lower bound for the optimal DRPP value is obtained by using cutting plane techniques, producing an optimal solution in 21 out of 60 instances. The main purpose of this work is to compare these three algorithms. We also give guidelines concerning the performance of the algorithms depending on the characteristics of the problem to solve.     

Models for Allocating Police Preventive Patrol Effort

This paper develops models that maximize the expected number of occasions per unit of time that a police patrol unit enters a street segment during the time that a crime is visible. Constraints are added that insure a minimum patrol coverage to all streets. The successive visits from street-to-street form a Markov chain. The solution that maximizes the objective function gives a stochastic decision rule which is used with Monte Carlo techniques to generate a random patrol schedule. The problem is posed with one car and several cars patrolling the same region.     

A Tabu Search Approach for the Prize Collecting Traveling Salesman Problem

The Prize Collecting Traveling Salesman Problem is a generalization of the Traveling Salesman Problem. A salesman collects a prize for each visited city and pays a penalty for each non visited city. The objective is to minimize the sum of the travel costs and penalties, but collecting a minimum pre-established amount of prizes. This problem is here addressed by a simple, but efficient tabu search approach which had improved several upper bounds of the considered instances.     

A General Vehicle Routing Problem

In this paper, we study a rich vehicle routing problem incorporating various complexities found in real-life applications. The General Vehicle Routing Problem (GVRP) is a combined load acceptance and generalised vehicle routing problem. Among the real-life requirements are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, orders with multiple pickup, delivery and service locations, different start and end locations for vehicles, and route restrictions for vehicles. The GVRP is highly constrained and the search space is likely to contain many solutions such that it is impossible to go from one solution to another using a single neighbourhood structure. Therefore, we propose iterative improvement approaches based on the idea of changing the neighbourhood structure during the search.     

The travelling salesperson problem with hotel selection

In this paper, we present the travelling salesperson problem with hotel selection (TSPHS), an extension of the TSP with a number of interesting applications. We present a mathematical formulation, explain the difference with related optimization problems and indicate what makes this problem inherently more difficult. We develop a simple but efficient heuristic that uses two constructive initialization procedures and an improvement procedure consisting of several neighbourhood search operators designed specifically for this problem, as well as some typical neighbourhoods from the literature. We generate several benchmark instances of varying sizes and compare the performance of our heuristic with CPLEX (10.0). We also generate some problems with known optimal solutions and use these to further demonstrate that our heuristic achieves good results in very limited computation times.     

Scheduling trucks in local depots for door-to-door delivery services

A scheduling method is suggested for trucks delivering and picking up freight between branch offices and a regional depot in door-to-door delivery services. As the objective functions, different levels of customer service resulting from different timing of deliveries and pickups to/from branch offices are considered as well as the travel cost of trucks. Useful properties of the optimal timing of deliveries and pickups are derived to reduce the size of the search space significantly. Numerical experiments were conducted to evaluate various algorithms to solve the problem.     

Three Value Estimates of Input Variables and Health Manpower Projections

The introduction of variability and stochastic processes in health manpower projections may help health planners cope with the inherent problem of uncertainty in the future. However, limited data and the complex nature of health manpower make it very difficult or even impossible to estimate the probability distribution of input variables. In this paper, two statistical methods are discussed and compared for approximating a probability distribution based on imperfect data. The common feature of the two methods is that they use minimum, maximum, and most likely values, which can be estimated by people with little knowledge of statistics and probability. In addition, the methods can be used to analyse variables with a symmetrical as well as non-symmetrical probability distribution. An example is provided of the application of the methods to health manpower projections in China.     

抛物型偏微分方程奇异摄动问题的边界层方法

本文讨论抛物型偏微分方程奇异摄动问题,通常,为了使边界层的特性不致丧失,在边界层附近必须减小网格,当网格足够小时需要很大的运算量。我们提出边界层格式,在边界层附近不必取很细的网格,数值例子表明采用中等步长即可满足精度。     

The Snow Disposal Assignment Problem

Snow removal and disposal are expensive winter activities that affect the quality of life and the environment in cities throughout the world. To facilitate traffic flow in urban regions that receive heavy snowfall, snow is first ploughed from streets and sidewalks and then hauled to disposal sites. A city is typically divided into many sectors that are cleared of snow concurrently. This paper briefly describes urban snow removal and disposal operations and analyses the snow disposal assignment problem for assigning snow removal sectors to snow disposal sites. The snow disposal assignment problem is formulated as a multi-resource generalized assignment problem. A two-phase heuristic solution procedure is developed, and solutions and sensitivity analyses are presented using data for the City of Montreal.     

EVE-OPT: a hybrid algorithm for the capacitated vehicle routing problem

This paper presents EVE-OPT, a Hybrid Algorithm based on Genetic Algorithms and Taboo Search for solving the Capacitated Vehicle Routing Problem. Several hybrid algorithms have been proposed in recent years for solving this problem. Despite good results, they usually make use of highly problem-dependent neighbourhoods and complex genetic operators. This makes their application to real instances difficult, as a number of additional constraints need to be considered. The algorithm described here hybridizes two very simple heuristics and introduces a new genetic operator, the Chain Mutation, as well as a new mutation scheme. We also apply a procedure, the k-chain-moves, able to increase the neighbourhood size, thereby improving the quality of the solution with negligible computational effort. Despite its simplicity, EVE-OPT is able to achieve the same results as very complex state-of-the art algorithms.     

Planning Urban Recreational Facilities with Integer Goal Programming

Urban planners are often involved in the determination of where recreational facilities (i.e. pools, gymnasia, tennis courts, etc.) should be located within the city. This problem is complicated by the planners' desire to realize certain goals in the allocation process. They desire to build only facilities for which there are sufficient construction funds and which can be operated within a predetermined budget. In addition they desire to satisfy the demands of the residents of the city for different facilities. However, these demands are often conflicting since many urban areas are somewhat segregated with the inner city being predominantly minority/lower income and the outer city consisting of white/upper income groups. These different groups enjoy different types of recreation, and, thus, demand different facilities. Since this is basically an allocation problem with multiple conflicting objectives, goal programming surfaces as an appropriate solution technique. This paper describes an integer (0-1) goal programming model for the recreational allocation problem and demonstrates its use via a case example. The model results specify the facilities which should be constructed that best meet the conflicting goals.     

Heuristics for multiple facility location in a network using the variance criterion

In cyclic networks the p-variance location problem is NP-hard, and therefore it is suitable to use heuristic methods to find approximate solutions to the problem. To this end, two strategies are explored, the first using combinatorial search procedures over the vertex set, whereas the second searches for the solution over the entire network. The initial vertex set solutions are generated by using tabu search, variable neighbourhood search and interchange procedures. The heuristics have been tested on instances of up to 30 vertices and 70 edges, and their performances compared.     

Traffic assignment model with fuzzy level of travel demand: An efficient algorithm based on quasi-Logit formulas

The place of fuzzy concepts in traffic assignment (TA) models has been studied in recent literature. Keeping fuzzy level of travel demand in mind, we propose a new TA model in which the travel costs of links are depended on their congestion. From the results of such fuzzy TA model, network planners are able to estimate the number of travelers on network links. By using zero–one variables, the proposed model is transformed into a crisp mixed-integer problem with respect to path-flow variables. In order to produce the Logit flows from this problem, Damberg et al. algorithm is modified. Then, the level of certainty is maximized and perceived travel delays are minimized. For a fixed certainty degree, the obtained solution, which is named the fuzzy equilibrium flow, satisfies a quasi-Logit formula similar to ordinary expression of the Logit route choice model. Eventually, we examine the quality of different path enumeration techniques in the proposed model.     

A simultaneous bus route design and frequency setting problem for Tin Shui Wai,Hong Kong

A bus network design problem for Tin Shui Wai, a suburban residential area in Hong Kong, is investigated, which considers the bus services from the origins inside this suburban area to the destinations in the urban areas. The problem aims to improve the existing bus services by reducing the number of transfers and the total travel time of the users. This has been achieved by the proposed integrated solution method which can solve the route design and frequency setting problems simultaneously. In the proposed solution method, a genetic algorithm, which tackles the route design problem, is hybridized with a neighborhood search heuristic, which tackles the frequency setting problem. A new solution representation scheme and specific genetic operators are developed so that the genetic algorithm can search all possible route structures, rather than selecting routes from the predefined set. To avoid premature convergence, a diversity control mechanism is incorporated in the solution method based on a new definition of hamming distance. To illustrate the robustness and quality of solutions obtained, computational experiments are performed based on 1000 perturbed demand matrices. The t-test results show that the design obtained by the proposed solution method is robust under demand uncertainty, and the design is better than both the current design and the design obtained by solving the route design problem and the frequency setting problem sequentially. Compared with the current bus network design, the proposed method can generate a design which can simultaneously reduce the number of transfers and total travel time at least by 20.9% and 22.7% respectively. Numerical studies are also performed to illustrate the effectiveness of the diversity control mechanism introduced and the effects of weights on the two objective values.     

A travel-time model for a person-onboard order picking system

The design of an order picking system in a distribution center depends on several decisions, where a key decision is determining the optimal storage system configuration (the number, length, and height of the storage aisles). To make this decision, a throughput model that considers vertical, as well as horizontal, travel is needed. In this paper we extend prior research that considers horizontal travel for a given number and length of the storage aisles so that we are also able to consider the height of the aisles as well. Such a model will provide a more accurate estimate of the throughput of an order picker and it will also permit an examination of the tradeoff between the length and height of the aisles. The analytical model we develop to estimate throughput is based on probability models and order statistics results assuming random storage. It is intended for person-onboard order picking systems and we consider both Tchebychev and rectilinear travel. We illustrate the use of our travel-time model by incorporating it into a simple, cost-based optimization model to recommend the height of a one-pallet-deep storage system.     

A model for the periodic optimization of bus dispatching times

We model the problem of dispatching time control in rolling horizons following a periodic optimization approach reactionary to travel time and passenger demand disturbances. This model provides more flexibility to transport planners allowing them to adjust the bus schedules during the daily operations. We prove that our periodic optimization model is a convex quadratic program, guaranteeing the global optimality of its solution. To reduce the computational burden, we introduce an iterative algorithm that uses gradient approximations to obtain an approximate dispatching solution. The proposed solution method is found to be significantly faster than exact optimization approaches for quadratic programming and maintains an (almost) negligible optimality gap in realistic bus operation scenarios. Finally, we show that our periodic optimization method outperforms myopic methods that adjust the dispatching time of each bus trip in isolation using operational data from bus line 302 in Singapore.