Location-allocation on congested networks

This paper deals with location-allocation decisions in networks under conditions of congestion, i.e. taking into consideration the possible arrival of calls for service while no server is available. The problem is to find simultaneously the optimal districting policy which determines how a region should be partitioned into separate service areas, and the optimal locations of facilities to house the service units. An alternate location and allocation solution improvement procedure is developed to combine an existing location algorithm of a single mobile service unit [3] with an existing districting heuristic for two servers [5]. The 2-server districting heuristic is further extended to treat the general case of m servers, and combined with the location algorithm for a single server it forms a general location-allocation heuristic for n nodes and m servers.     

A Fast,Network-based,Hybrid Heuristic for the Assignment of Students to Schools

In an era of declining and fluctuating enrolments, the determination of appropriate school sizes and student assignments poses difficult problems for administrators. For two decades, researchers have worked with variants of a linear programming districting model which minimizes total weighted distance as all students are assigned to schools constrained by both capacity and racial balance limitations. This model could aid in the generation of districting alternatives, but is difficult to solve in realistic applications with generalized solution procedures because of overall problem size. This has prompted the development of fast, network-based models, solvable with special algorithms and codes. We show, however, that these approaches all contain major shortcomings. We present a fast, hybrid heuristic based upon two network representations. Computational results demonstrate this to be a very fast solution approach for the general case of this districting problem.     

Designing delivery districts for the vehicle routing problem with stochastic demands

This paper considers the problem of designing districts for vehicle routing problems with stochastic demands. In particular, demands are assumed to be uncertain at the time when the districts are made, and these are revealed only after the districting decisions are determined. Tabu search and multistart heuristics for this stochastic districting problem are developed and compared. Computational results show that tabu search is superior over multistart.     

Computing sharp bounds for hard clustering problems on trees

Clustering problems with relational constraints in which the underlying graph is a tree arise in a variety of applications: hierarchical data base paging, communication and distribution networks, districting, biological taxonomy, and others. They are formulated here as optimal tree partitioning problems. In a previous paper, it was shown that their computational complexity strongly depends on the nature of the objective function and, in particular, that minimizing the total within-cluster dissimilarity or the diameter is computationally hard. We propose heuristics that find good partitions within a reasonable time, even for instances of relatively large size. Such heuristics are based on the solution of continuous relaxations of certain integer (or almost integer) linear programs. Experimental results on over 2000 randomly generated instances with up to 500 entities show that the values (total within-cluster dissimilarity or diameter) of the solutions provided by these heuristics are quite close to the minimum one.     

District design for arc-routing applications

In this paper we address the problem of district design for the organisation of arc-routing activities. In particular, the focus is on operations like winter gritting and road maintenance. The problem involves how to allocate the road network edges to a set of depots with given locations. The collection of edges assigned to a facility forms a district in which routes have to be designed that start and end at the facility. Apart from the ability to support good arc routing, well-designed districts for road-maintenance operations should have the road network to be serviced connected and should define clear geographical boundaries. We present three districting heuristics and evaluate the quality of the partitions by solving capacitated arc routing problems in the districts, and by comparing the solution values with a multi-depot CARP cutting plane lower bound. Our experiments reveal that based on global information about the distribution system (ie the number of facilities or districts, the average edge demand and the vehicle capacity) and by using simple guidelines, an adequate districting policy may be selected.     

A Simulated Annealing Genetic Algorithm for the Electrical Power Districting Problem

Due to a variety of political, economic, and technological factors, many national electricity industries around the globe are transforming from non-competitive monopolies with centralized systems to decentralized operations with competitive business units. A key challenge faced by energy restructuring specialists at the World Bank is trying to simultaneously optimize the various criteria one can use to judge the fairness and commercial viability of a particular power districting plan. This research introduces and tests a new algorithm for solving the electrical power districting problem in the context of the Republic of Ghana and using a random test problem generator. We show that our mimetic algorithm, the Simulated Annealing Genetic Algorithm, outperforms a well-known Parallel Simulated Annealing heuristic on this new and interesting problem manifested by the deregulation of electricity markets.     

Routing,districting and location for arc traversal problems

We summarize the main results of the authors PhD thesis, defended in February 2003 at the Katholieke Universiteit Leuven (Belgium) and supervised by Dirk Cattrysse. The thesis is written in English and presents a number of solution and modeling approaches for distribution problems in the context of arc routing. In particular, the focus is on (1) local search procedures for arc routing problems, (2) district design for arc routing applications and (3) the study of location aspects in relation with districting and arc routing.AMS classification: 90B06, 05C38, 90C35, 90C59     

Clustering for routing in densely populated areas

This paper introduces a new approach for generating school bus routes in a dense urban area. First, a districting algorithm is used to determine clusters including appropriate numbers of students. Then, for each cluster, a route and the stops along this route are determined. Numerical results are reported and compared with those obtained previously. Although the algorithm has been developped and tested in a specific context, it could easily be extended to more general vehicle routing problems.     

Political districting: from classical models to recent approaches

The political districting problem has been studied since the 60’s and many different models and techniques have been proposed with the aim of preventing districts’ manipulation which may favor some specific political party (gerrymandering). A variety of political districting models and procedures was provided in the Operations Research literature, based on single- or multiple-objective optimization. Starting from the forerunning papers published in the 60’s, this article reviews some selected optimization models and algorithms for political districting which gave rise to the main lines of research on this topic in the Operartions Research literature of the last five decades.     

Solving a home-care districting problem in an urban setting

This article describes a districting study undertaken for the Côte-des-Neiges local community health clinic in Montreal. A territory must be partitioned into six districts by suitably grouping territorial basic units. Five districting criteria must be respected: indivisibility of basic units, respect for borough boundaries, connectivity, visiting personnel mobility, and workload equilibrium. The last two criteria are combined into a single objective function and the problem is solved by means of a tabu search technique that iteratively moves a basic unit to an adjacent district or swaps two basic units between adjacent districts. The problem was solved and the clinic management confirmed its satisfaction after a 2 year implementation period.     

An optimization approach for ambulance location and the districting of the response segments on highways

In this paper we present a method to optimize the configuration and operation of emergency medical systems on highways. Different from the approaches studied in the previous papers, the present method can support two combined configuration decisions: the location of ambulance bases along the highway and the districting of the response segments. For example, this method can be used to make decisions regarding the optimal location and coverage areas of ambulances in order to minimize mean user response time or remedy an imbalance in ambulance workloads within the system. The approach is based on embedding a well-known spatially distributed queueing model (hypercube model) into a hybrid genetic algorithm to optimize the decisions involved. To illustrate the application of the proposed method, we utilize two case studies on Brazilian highways and validate the findings via a discrete event simulation model.     

A districting procedure for social organizations

The problem dealt with in the paper refers to the decomposition of a geographical region into an unspecified number of non-overlapping regional partitions. Each partition is given by a connected aggregation of indivisible elementary areas and must contain at least one source of a certain social service characterized by assigned capacity and location. Each area is characterized by a service demand and by a measure quantifying its dimension.Two heuristic methods are proposed to obtain a preliminary aggregation of the elementary areas, in order to reduce the computational effort involved in generating the feasible partitions. A fuzzy sets approach is presented for rating and ranking the regional partitions. This approach seems to be particularly suited to planning problems, when some kind of compromise between qualitative and quantitative issues must be sought. A health-care districting problem is then discussed as a case study.     

School redistricting: embedding GIS tools with integer programming

The paper deals with a school redistricting problem in which blocks of a city must be assigned to schools according to diverse criteria. Previous approaches are reviewed and some desired properties of a good school districting plan are established. An optimization model together with a geographic information system environment are then proposed for finding a solution that satisfies these properties. A prototype of the system is described, some implementation issues are discussed, and two real-life examples from the city of Philadelphia are studied, one corresponding to a relatively easy to solve problem, and the other to a much harder one. The trade-offs in the solutions are analysed and feasibility questions are discussed. The results of the study strongly suggest that ill-defined spatial problems, such as school redistricting, can be addressed effectively by an interaction between objective analysis and subjective judgement.     

A note on optimal stopping of diffusions with a two-sided optimal rule

We consider a class of optimal stopping problems of diffusions with a two-sided optimal rule. We propose an approach for finding and characterizing the solution. We establish that the optimal stopping rule can be associated with the unique fixed point of an auxiliary function. The results are illustrated with an explicit example.     

Study of optimal control problems on the half-line by the averaging method

We justify the application of the averaging method to optimal control problems for systems of differential equations on the half-line. For optimal control problems for systems of differential equations linear in the control, we prove the existence of optimal controls for the exact and averaged problems. We show that an optimal control in the averaged problem is ɛ-optimal in the exact problem.     

Continuous approximation models in freight distribution management

This paper presents an overview of the literature on continuous approximation models in the context of distribution management. It first describes the seminal contributions of Beardwood, Halton and Hammersley, and of Daganzo and Newell. This is followed by a summary of various extensions, and by applications to districting, location, fleet sizing and vehicle routing.     

On the optimal control of a class of non-Newtonian fluids

We consider optimal control problems of systems governed by stationary, incompressible generalized Navier–Stokes equations with shear dependent viscosity in a two-dimensional or three-dimensional domain. We study a general class of viscosity functions with shear-thinning and shear-thickening behavior. We prove an existence result for such class of optimal control problems.     

On the uniqueness of optimal solutions in continuous location theory

This paper deals with the uniqueness of an optimal solution in general continuous single facility minisum and minimax location problems. We define the concept of an S-norm and obtain general conditions which guarantee the existence of a unique optimal location. Some consequences for the uniqueness of optimal locations in multi-facility location problems are discussed.     

Uniqueness of the solution for optimal static routing in open BCMP queueing networks

Optimal static routing problems in open BCMP queueing networks with state-independent arrival and service rates are studied. They include static routing problems in communication networks and optimal static load balancing problems in distributed computer systems. We consider an overall optimal policy that is the routing policy whereby the overall mean response (or sojourn) time of a job is minimized. We obtain the routing decisions of the overall optimal policy and show that they may not be unique, but that the utilization of each service center is uniquely determined by the overall optimal policy. We also consider an individually optimal policy whereby jobs are routed so that each job may feel that its own expected response time is minimized if it knows the mean delay time for each path.