Joint inventory-location problem under the risk of probabilistic facility disruptions

This paper studies a reliable joint inventory-location problem that optimizes facility locations, customer allocations, and inventory management decisions when facilities are subject to disruption risks (e.g., due to natural or man-made hazards). When a facility fails, its customers may be reassigned to other operational facilities in order to avoid the high penalty costs associated with losing service. We propose an integer programming model that minimizes the sum of facility construction costs, expected inventory holding costs and expected customer costs under normal and failure scenarios. We develop a Lagrangian relaxation solution framework for this problem, including a polynomial-time exact algorithm for the relaxed nonlinear subproblems. Numerical experiment results show that this proposed model is capable of providing a near-optimum solution within a short computation time. Managerial insights on the optimal facility deployment, inventory control strategies, and the corresponding cost constitutions are drawn.     

Stochastic capacity expansion models for airport facilities

It is important and also challenging to plan airport facilities to meet future traffic needs in a rapidly changing environment, which is characterized by various uncertainties. One key issue in airport facility development is that facility performance functions (delay levels as functions of capacity utilization rates) are nonlinear, which complicates the solution method design. Potential demand fluctuations in a deregulated aviation market add another dimension to the decision making process. To solve this problem, a deterministic total cost minimization model is proposed and then extended into stochastic programs, by including uncertainties in traffic forecasts. After the exploration of properties of the delay cost function, an Outer-Approximation (OA) technique which is superior to the existing discrete approximation is designed. After model enhancements, an efficient solution framework based on the OA technique is used to solve the model to its global optimality by interactively generating upper and lower bounds to the objective. Computational tests demonstrate the validity of developed models and efficiency of proposed algorithms. The total cost is reduced by 18.8% with the stochastic program in the numerical example.     

Robust optimization of distance-based tolls in a network considering stochastic day to day dynamics

This paper investigates the nonlinear distance-based congestion pricing in a network considering stochastic day-to-day dynamics. After an implementation/adjustment of a congestion pricing scheme, the network flows in a certain period of days are not on an equilibrium state, thus it is problematic to take the equilibrium-based indexes as the pricing objective. Therefore, the concept of robust optimization is taken for the congestion toll determination problem, which takes into account the network performance of each day. First, a minimax model which minimizes the maximum regret on each day is proposed. Taking as a constraint of the minimax model, a path-based day to day dynamics model under stochastic user equilibrium (SUE) constraints is discussed in this paper. It is difficult to solve this minimax model by exact algorithms because of the implicity of the flow map function. Hence, a two-phase artificial bee colony algorithm is developed to solve the proposed minimax regret model, of which the first phase solves the minimal expected total travel cost for each day and the second phase handles the minimax robust optimization problem. Finally, a numerical example is conducted to validate the proposed models and methods.     

Robust intermodal hub location under polyhedral demand uncertainty

In this study, we consider the robust uncapacitated multiple allocation p-hub median problem under polyhedral demand uncertainty. We model the demand uncertainty in two different ways. The hose model assumes that the only available information is the upper limit on the total flow adjacent at each node, while the hybrid model additionally imposes lower and upper bounds on each pairwise demand. We propose linear mixed integer programming formulations using a minmax criteria and devise two Benders decomposition based exact solution algorithms in order to solve large-scale problems. We report the results of our computational experiments on the effect of incorporating uncertainty and on the performance of our exact approaches.     

A reliable location model for heterogeneous systems under partial capacity losses

Due to the interdependency between multiple infrastructure systems, the performance of a facility may depend on the resources or supplies received from other facilities. However, cross-system interdependence has seldom been studied in the location design context, probably due to the lack of a concise model describing interdependence across heterogeneous systems. This paper proposes a new heterogeneous flow scheme to describe cross-system interdependence. This scheme has two features distinguished from existing models in describing an interdependent facility location problem. First, it is a simple linear model upon which a compact facility location model can be built. Secondly, it relaxes the need to maintain flow conservation between different systems and is suitable in describing heterogeneous systems that take in and output different resources or services. Built on this scheme, this paper proposes a reliable location design model for a nexus of interdependent infrastructure systems. This model aims to locate the optimal facility locations in multiple heterogeneous systems to balance the tradeoff between the facility investment and the expected nexus operation performance. Different from other reliable facility location models, this expected performance captures interdependence among heterogeneous systems due to the resource input-output relationships. The consideration of continuous partial capacity losses complements the reliable location literature that mainly focuses on binary disruptions. Two numerical examples are conducted for investigating features and applications of the proposed model. The results indicate that with a standard off-the-shelf integer programming solver, the proposed model is able to solve optimal facility location design for problem instances of realistic scales to the near-optimum solutions with optimality gap assurance. Sensitivity analyses of key parameters indicate that improving facility capacity and reducing interdependency between systems can mitigate impacts of facility capacity losses and reduce the overall system cost.     

Reliable sensor deployment for network traffic surveillance

New sensor technologies enable synthesis of disaggregated vehicle information from multiple locations. This paper proposes a reliable facility location model to optimize traffic surveillance benefit from synthesized sensor pairs (e.g., for travel time estimation) in addition to individual sensor flow coverage (e.g., for traffic volume statistics), while considering probabilistic sensor failures. Customized greedy and Lagrangian relaxation algorithms are proposed to solve this problem, and their performance is discussed. Numerical results show that the proposed algorithms solve the problem efficiently. We also discuss managerial insights on how optimal sensor deployment and surveillance benefits vary with surveillance objective and system parameters (such as sensor failure probabilities).     

Sequential optimization approach for the multi‐class user equilibrium problem in a continuous transportation system

We consider a city region with several facilities that are competing for customers of different classes. Within the city region, the road network is dense, and can be represented as a continuum. Customers are continuously distributed over space, and they choose a facility by considering both the transportation cost and market externalities. More importantly, the model takes into account the different transportation cost functions and market externalities to which different customer classes are subjected. A logit‐type distribution of demand is specified to model the decision‐making process of users' facility choice. We develop a sequential optimization approach to decompose the complex multi‐class and multi‐facility problem into a series of smaller single‐class and single‐facility sub‐problems. An efficient solution algorithm is then proposed to solve the resultant problem. A numerical example is given to demonstrate the effectiveness and potential applicability of the proposed methodology.     

Passenger-demands-oriented train scheduling for an urban rail transit network

This paper considers the train scheduling problem for an urban rail transit network. We propose an event-driven model that involves three types of events, i.e., departure events, arrival events, and passenger arrival rates change events. The routing of the arriving passengers at transfer stations is also included in the train scheduling model. Moreover, the passenger transfer behavior (i.e., walking times and transfer times of passengers) is also taken into account in the model formulation. The resulting optimization problem is a real-valued nonlinear nonconvex problem. Nonlinear programming approaches (e.g., sequential quadratic programming) and evolutionary algorithms (e.g., genetic algorithms) can be used to solve this train scheduling problem. The effectiveness of the event-driven model is evaluated through a case study.     

A mixed-integer linear program for optimizing sensor locations along freeway corridors

How to optimally allocate limited freeway sensor resources is of great interest to transportation engineers. In this paper, we focus on the optimal allocation of point sensors, such as loop detectors, to minimize performance measurement errors. Although it has been shown that the minimization problem can be intuitively formulated as a nonlinear program, the formulation is so complex that only heuristic approaches can be used to solve the problem. In this paper, we transform the nonlinear program into an equivalent mixed-integer linear model. The linearized model is shown to have a graphical interpretation and can be solved using resource constrained shortest path algorithms. A customized Branch-and-Bound technique is then proposed to solve the resource constrained shortest path problem. Numerical experiments along an urban freeway corridor demonstrate that this sensor location model is successful in allocating loop detectors to improve the accuracy of travel time estimation.     

System optimal dynamic traffic assignment: Properties and solution procedures in the case of a many-to-one network

Thanks to its high dimensionality and a usually non-convex constraint set, system optimal dynamic traffic assignment remains one of the most challenging problems in transportation research. This paper identifies two fundamental properties of the problem and uses them to design an efficient solution procedure. We first show that the non-convexity of the problem can be circumvented by first solving a relaxed problem and then applying a traffic holding elimination procedure to obtain the solution(s) of the original problem. To efficiently solve the relaxed problem, we explore the relationship between the relaxed problems based on different traffic flow models (PQ, SQ, CTM) and a minimal cost flow (MCF) problem for a special space-expansion network. It is shown that all the four problem formulations produce the same minimal system cost and share one common solution which does not involve inside queues in the network. Efficient solution algorithms such as the network simplex method can be applied to solve the MCF problem and identify such an optimal traffic pattern. Numerical examples are also presented to demonstrate the efficiency of the proposed solution procedure.     

Robust weekly aircraft maintenance routing problem and the extension to the tail assignment problem

In this paper, we study two closely related airline planning problems: the robust weekly aircraft maintenance routing problem (RWAMRP) and the tail assignment problem (TAP). In real life operations, the RWAMRP solution is used in tactical planning whereas the TAP solution is implemented in operational planning. The main objective of these two problems is to minimize the total expected propagated delay (EPD) of the aircraft routes. To formulate the RWAMRP, we propose a novel weekly line-of-flights (LOF) network model that can handle complex and nonlinear cost functions of EPD. Because the number of LOFs grows exponentially with the number of flights to be scheduled, we propose a two-stage column generation approach to efficiently solve large-scale real-life RWAMRPs. Because the EPD of an LOF is highly nonlinear and can be very time-consuming to accurately compute, we propose three lower bounds on the EPD to solve the pricing subproblem of the column generation. Our approach is tested on eight real-life test instances. The computational results show that the proposed approach provides very tight LP relaxation (within 0.6% of optimal solutions) and solves the test case with more than 6000 flights per week in less than three hours. We also investigate the solutions obtained by our approach over 500 simulated realizations. The simulation results demonstrate that, in all eight test instances, our solutions result in less EPDs than those obtained from traditional methods. We then extend our model and solution approach to solve realistically simulated TAP instances.     

A stochastic model for highway traffic

A nonlinear model for unidirectional flow of heavy traffic on a two-lane highway is considered. Features such as entrance, exit and lane transfer with time-dependent parameters are incorporated into the model, with the result that a number of previous models employed in the study of traffic flow become special cases of ours. Using the method of system-size expansion, an asymptotic analysis of the problem, including the time evolution of both deterministic and stochastic aspects of the traffic system, is carried out. In addition, a scheme for obtaining the moments of the probability distribution for systems of finite size is developed and a comparison is made with the exact results appropriate to a particular model. The agreement between the two sets of results turns out to be remarkably good.     

Liner ship route schedule design with port time windows

This paper examines a practical tactical liner ship route schedule design problem, which is the determination of the arrival and departure time at each port of call on the ship route. When designing the schedule, the availability of each port in a week, i.e., port time window, is incorporated. As a result, the designed schedule can be applied in practice without or with only minimum revisions. This problem is formulated as a mixed-integer nonlinear nonconvex optimization model. In view of the problem structure, an efficient holistic solution approach is proposed to obtain global optimal solution. The proposed solution method is applied to a trans-Atlantic ship route. The results demonstrate that the port time windows, port handling efficiency, bunker price and unit inventory cost all affect the total cost of a ship route, the optimal number of ships to deploy, and the optimal schedule.     

Scheduled paratransit transport systems

In this paper we focus on ways to provide individualized services to people with mobility challenges using existing modes of public transport. We study the design of an interesting case, in which a bus operating in a public transport route may diverge from its nominal path to pick-up passengers with limited mobility and drop them off at their destination. We have modeled the design problem by a mixed integer-linear program, and we developed an exact Branch and Price approach to solve it to optimality. The proposed approach includes a labeling algorithm in which we introduced appropriate dominance rules, which do not compromise optimality. We have compared the efficiency of our approach with that of related algorithms from the literature. Furthermore, we have used the proposed approach to study key aspects of the system design problem, such as the effect of various constraints on the service level, and the tuning of the system’s parameters to address different transport environments.     

Optimal scheduling of a taxi fleet with mixed electric and gasoline vehicles to service advance reservations

This study addresses the problem of scheduling a fleet of taxis that are appointed to solely service customers with advance reservations. In contrast to previous studies that have dealt with the planning and operations of a taxi fleet with only electric vehicles (EVs), we consider that most taxi companies may have to operate with fleets comprised of both gasoline vehicles (GVs) and plug-in EVs during the transition from GV to (complete) EV taxi fleets. This paper presents an innovative multi-layer taxi-flow time-space network which effectively describes the movements of the taxis in the dimensions of space and time. An optimization model is then developed based on the time-space network to determine an optimal schedule for the taxi fleet. The objective is to minimize the total operating cost of the fleet, with a set of operating constraints for the EVs and GVs included in the model. Given that the model is formulated as an integer multi-commodity network flow problem, which is characterized as NP-hard, we propose two simple but effective decomposition-based heuristics to efficiently solve the problem with practical sizes. Test instances generated based on the data provided by a Taiwan taxi company are solved to evaluate the solution algorithms. The results show that the gaps between the objective values of the heuristic solutions and those of the optimal solutions are less than 3%, and the heuristics require much less time to obtain the good quality solutions. As a result, it is shown that the model, coupled with the algorithms, can be an effective planning tool to assist the company in routing and scheduling its fleet to service reservation customers.     

Bicriterion shortest path problem with a general nonadditive cost

A bicriterion shortest path problem with a general nonadditive cost seeks to optimize a combination of two path costs, one of which is evaluated by a nonlinear function. This paper first identifies a number of emerging transportation applications for which such a shortest path problem might be considered a core subproblem. We propose to first approximate the general nonlinear cost function with a piecewise linear counterpart, and then solve each linear subproblem sequentially. A specialized algorithm is developed to solve the subproblems, which makes use of the efficient path set (or the convex hull) to update upper and lower bounds of the original problem. Conditions under which the solution to a subproblem must belong to the efficient path set are specified. Accordingly, we show that the optimal path must be efficient if the nonlinear cost function is concave. If the optimal path to a subproblem is not efficient, partial path enumeration, implemented using a simple K-shortest path ranking procedure, is conducted to close the gap. The proposed algorithm includes strategies aiming to expedite path enumeration by using upper bounds derived from the efficient path set. Numerical experiments are conducted to demonstrate correctness and effectiveness of the proposed algorithm.     

Determining intermediate origin-destination matrices for the analysis of composite mode trips

We consider in this paper the problem of determining intermediate origin-destination matrices for composite mode trips that involve a trip by private car to a parking facility and the continuation of the trip to the destination either by walking or by a transit mode. The intermediate origin-destination matrices relate to each component of the composite mode trip: a matrix from the trip origins to intermediate destinations which are parking lots and a matrix from the parking lots to the final destinations. The approach that we propose to solve this problem is to modify the entropy based trip distribution models to consider inequality constraints related to parking lot capacities. Such models may be easily calibrated by using well known calibration methods or generalization of these methods and may be easily solved by applying a primal feasible direction method of nonlinear programming.     

Comparative tests of multimodal traffic equilibrium methods

In this study we proceeded to test the relative efficiencies of the two main computational techniques now available for calculating the traffic equilibrium in multimodal networks, namely, the relaxation and projection methods. Since both of these methods solve at each step a mathematical programming problem, we first set out to test the Frank-Wolfe algorithm and the Dafermos-Sparrow algorithm and found the latter to be the more efficient algorithm. As expected, this was also the case when these algorithms were used to solve the mathematical programming problem at each step of the relaxation method. We then investigated how different versions of the projection method enhance its performance. Subsequently, we proceeded to our main goal to compare the best projection method with the relaxation method. We tested multimodal networks with three different classes of monotone travel cost functions and found that the form of the travel cost functions affects the performance of the two basic techniques available for computing the multimodal equilibrium.     

Inter-city bus routing and timetable setting under stochastic demands

Vehicle fleet routing and timetable setting are essential to the enhancement of an inter-city bus carrier’s operating cost, profit, level of service and competitiveness in the market. In past research the average passenger demand has usually served as input in the production of the final fleet routes and timetables, meaning that stochastic disturbances arising from variations in daily passenger demand in actual operations are neglected. To incorporate the stochastic disturbances of daily passenger demands that occur in actual operations, in this research, we established a stochastic-demand scheduling model. We applied a simulation technique, coupled with link-based and path-based routing strategies, to develop two heuristic algorithms to solve the model. To evaluate the performance of the proposed model and the two solution algorithms, we developed an evaluation method. The test results, regarding a major Taiwan inter-city bus operation, were good, showing that the model and the solution algorithms could be useful in practice.