Transportation Science

This paper considers integrated location and routing models for minimizing the expected number of hazardous material transport accidents. Two different routing policies are considered: (1) most reliable route planning and (2) multiple routing with random selection. Path reliability measurements are used to derive the expected number of accidents over a given planning horizon, where reliability refers to the probability of completing a journey without accident. Corresponding to the two routing policies, two location models are introduced: the reliable 1-median and a location framework for considering multiple routes. Based on realistic assumptions for assigning accident probabilities to segments created when an edge location is considered, vertex optimality results for both problems are obtained. An example to illustrate reliable routing and location in Massachusetts is provided.

Classical facility location models like the P-median problem (PMP) and the uncapacitated fixed-charge location problem (UFLP) implicitly assume that, once constructed, the facilities chosen will always operate as planned. In reality, however, facilities “fail” from time to time due to poor weather, labor actions, changes of ownership, or other factors. Such failures may lead to excessive transportation costs as customers must be served from facilities much farther than their regularly assigned facilities. In this paper, we present models for choosing facility locations to minimize cost, while also taking into account the expected transportation cost after failures of facilities. The goal is to choose facility locations that are both inexpensive under traditional objective functions and also reliable. This reliability approach is new in the facility location literature. We formulate reliability models based on both the PMP and the UFLP and present an optimal Lagrangian relaxation algorithm to solve them. We discuss how to use these models to generate a trade-off curve between the day-to-day operating cost and the expected cost, taking failures into account, and we use these trade-off curves to demonstrate empirically that substantial improvements in reliability are often possible with minimal increases in operating cost.

The maximum covering location model has been used extensively in analyzing locations for public service facilities. The model is extended to account for the chance that when a demand arrives at the system it will not be covered since all facilities capable of covering the demand are engaged serving other demands. An integer programming formulation of the new problem is presented. Several properties of the formulation are proven. A heuristic solution algorithm is presented and computational results with the algorithm are discussed. Directions for future study are also discussed.

Mirchandani and Odoni have extended the concept of median location to stochastic networks, that is, networks where the distances (times) on some arcs and/or the demands at some nodes may be discrete random variables. Computational procedures for the solution of such median location problems on stochastic networks are developed; limited testing gave encouraging results.

This paper presents some improvements and some generalizations of existing techniques for computing a 1-center of a network and a p-center of a tree. For a network with n vertices and |E| edges the amount of computation to find a 1-center is shown to be at most 0(|E|n² log n) in the vertex weighted case and 0(|E|n log n) in the vertex unweighted; for a p-center of a tree (p > 1, unweighted case), the bound is 0(n^p−1).

The definition of network medians is extended to the case where travel times on network links are random variables with known discrete probability distributions. Under a particular set of assumptions, it is shown that the well known “facilities at nodes” theorems of Hakimi and of Levy can be extended to such stochastic networks. The concepts are further extended to the case of stochastic oriented networks. A particular set of applications, as well as mathematical programming formulations of the problem, are also discussed briefly.

The Maximal Expected Coverage Location Problem (MEXCLP) addresses the problem of optimally locating servers so as to maximize the expected coverage of demand while taking into account the possibility of servers being unavailable when a call enters the service system. In this paper, an attempt is made to relax three of MEXCLP's assumptions: servers operate independently, servers have the same busy probabilities, and server busy probabilities are invariant with respect to their locations. We embed the hypercube queueing model in a single node substitution heuristic optimization procedure, to determine a set of server locations which “maximize” the expected coverage. Our empirical findings indicate that there is disagreement between the expected coverage predicted by the MEXCLP model and the hypercube optimization procedure. There is substantial agreement, however, between the locations generated by the two procedures. We also consider a simple “adjustment” to the MEXCLP model, based upon random sampling of servers without replacement; the same adjustment has been used previously to derive a hypercube approximation procedure. We discuss modifications and enhancements to the MEXCLP's heuristic solution procedure for this adjusted model. Our empirical findings indicate that there is better agreement between the expected coverage predicted by the adjusted model and the hypercube optimization procedure. The locations generated by the adjusted model, however, are of the same overall quality as those generated by the MEXCLP model. Readers should view the results of this paper in light of the fact that we are able to relax the MEXCLP by assuming that the operating characteristics of the service system fit the description of the hypercube queueing model, such as Poisson arrivals and exponential service times, which may not be strictly true in practice.

In this paper we deal with networks whose link travel times are not constant but undergo random changes. As a result of these changes the network may be in a finite number of discrete states. The paper contains a heuristic that finds the optimal set of locations for a set a facilities (servers), which may be moved, at a cost, in response to changes in the state of the network. The heuristic is suitable for a general number of facilities (previous research dealt with a single facility). The heuristic, which executes in polynomial time, is compared to the exact solution of the integer linear programming version of the problem for a series of small examples. For larger examples, the solution of the heuristic is compared to several bounds. An efficient method for performing sensitivity analysis is also indicated.

Một vấn đề phổ biến mà các hãng vận tải gặp phải trong lĩnh vực vận tải tuyến là thiết kế mạng lưới dịch vụ của họ. Với một tập hợp các yêu cầu vận chuyển và một tập hợp các cảng, một hãng vận tải muốn thiết kế các lộ trình dịch vụ cho tàu của mình một cách hiệu quả nhất, sử dụng các cơ sở hạ tầng sẵn có. Hơn nữa, khả năng sinh lời của các lộ trình dịch vụ được thiết kế phụ thuộc vào các tuyến đường được chọn để vận chuyển hàng hóa. Chúng tôi trình bày một mô hình tích hợp, một chương trình tuyến tính hỗn hợp nguyên, để giải quyết đồng thời các vấn đề về lập lịch tàu và lộ trình hàng hóa. Mô hình đề xuất bao gồm các ràng buộc có liên quan, chẳng hạn như ràng buộc tần suất hàng tuần đối với các lộ trình hoạt động, và các xu hướng mới nổi như việc chuyển tải hàng hóa giữa hai hoặc nhiều lộ trình dịch vụ. Để giải quyết chương trình nguyên hỗn hợp, chúng tôi đề xuất các thuật toán khai thác tính tách rời của vấn đề. Cụ thể hơn, một phương pháp tham lam, một thuật toán dựa trên sinh cột, và một thuật toán phân rã Benders hai pha được phát triển, và hiệu suất tính toán của chúng về chất lượng giải pháp và thời gian tính toán được thảo luận. Một thuật toán tìm kiếm lặp hiệu quả được đề xuất để tạo ra lịch cho các tàu. Các thí nghiệm tính toán được tiến hành trên các trường hợp được sinh ngẫu nhiên mô phỏng thực tế với tối đa 20 cảng và 100 tàu. Kết quả của chúng tôi chỉ ra khả năng sử dụng công suất tàu cao và một số lượng đáng kể các chuyển tải trong giải pháp cuối cùng.

Một phiên bản xác suất của vấn đề định vị tối đa bao phủ được giới thiệu ở đây. Vấn đề tối đa hóa khả năng sẵn có (MALP) đặt p máy chủ ở những vị trí nhằm tối đa hóa dân số có khả năng tìm thấy một máy chủ sẵn có trong thời gian tiêu chuẩn với độ tin cậy α. Vấn đề tối đa hóa khả năng sẵn có dựa trên vấn đề bao phủ tập định vị xác suất về mặt khái niệm và trên các mô hình bao phủ sao lưu và bao phủ mong đợi về mặt chi tiết kỹ thuật. MALP có mối quan hệ tương tự với vấn đề bao phủ tập định vị xác suất như cách mà vấn đề bao phủ tối đa xác định có mối quan hệ với vấn đề bao phủ tập định vị xác định. Vấn đề tối đa hóa khả năng sẵn có được cấu trúc ở đây như một bài toán lập trình tuyến tính nhị phân và được giải quyết trên một mạng lưới vận tải có quy mô trung bình đại diện cho thành phố Baltimore.