Itinerary choice and advance ticket booking for high-speed-railway network services

This paper formulates and examines the passenger flow assignment (itinerary choice) problem in high-speed railway (HSR) systems with multiple-class users and multiple-class seats, given the train schedules and time-varying travel demand. In particular, we take into account advance booking cost of travelers in the itinerary choice problem. Rather than a direct approach to model advance booking cost with an explicit cost function, we consider advance booking cost endogenously, which is determined as a part of the passenger choice equilibrium. We show that this equilibrium problem can be formulated as a linear programming (LP) model based on a three-dimension network representation of time, space, and seat class. At the equilibrium solution, a set of Lagrange multipliers for the LP model are obtained, which are associated with the rigid in-train passenger capacity constraints (limited numbers of seats). We found that the sum of the Lagrange multipliers along a path in the three-dimension network reflects the advance booking cost of tickets (due to advance/early booking to guarantee availability) perceived by the passengers. Numerical examples are presented to demonstrate and illustrate the proposed model for the passenger assignment problem.     

The dynamic shortest path problem with time-dependent stochastic disruptions

The dynamic shortest path problem with time-dependent stochastic disruptions consists of finding a route with a minimum expected travel time from an origin to a destination using both historical and real-time information. The problem is formulated as a discrete time finite horizon Markov decision process and it is solved by a hybrid Approximate Dynamic Programming (ADP) algorithm with a clustering approach using a deterministic lookahead policy and value function approximation. The algorithm is tested on a number of network configurations which represent different network sizes and disruption levels. Computational results reveal that the proposed hybrid ADP algorithm provides high quality solutions with a reduced computational effort.     

A linear programming formulation for autonomous intersection control within a dynamic traffic assignment and connected vehicle environment

This paper develops a novel linear programming formulation for autonomous intersection control (LPAIC) accounting for traffic dynamics within a connected vehicle environment. Firstly, a lane based bi-level optimization model is introduced to propagate traffic flows in the network, accounting for dynamic departure time, dynamic route choice, and autonomous intersection control in the context of system optimum network model. Then the bi-level optimization model is transformed to the linear programming formulation by relaxing the nonlinear constraints with a set of linear inequalities. One special feature of the LPAIC formulation is that the entries of the constraint matrix has only {−1, 0, 1} values. Moreover, it is proved that the constraint matrix is totally unimodular, the optimal solution exists and contains only integer values. It is also shown that the traffic flows from different lanes pass through the conflict points of the intersection safely and there are no holding flows in the solution. Three numerical case studies are conducted to demonstrate the properties and effectiveness of the LPAIC formulation to solve autonomous intersection control.     

A multi‐objective approach to the parcel express service delivery problem

Parcel express service in many countries assumes door‐to‐door delivery of parcels and small packages in the fastest possible way. Delivery companies usually organize hub delivery networks, as flows between hubs are characterized by the economy of scale effect. At hubs, parcels are exchanged across vans, trucks, and planes. To organize parcel delivery in a specific region, the parcel delivery company must make appropriate decisions about the total number of parcel delivery hubs, their locations, and the allocation of demand for facilities' services to facilities. These issues are modeled in this paper as a multi‐objective problem. The model developed is based on compromise programming and genetic algorithms. We also demonstrate in the paper an interactive manner in which a defined problem can be solved. The proposed model could be implemented in large‐scale networks. The paper also shows a case study of parcel delivery service in Serbia. Copyright © 2013 John Wiley & Sons, Ltd.     

Vehicle routing with roaming delivery locations

We propose the vehicle routing problem with roaming delivery locations (VRPRDL) to model an innovation in last-mile delivery where a customer’s order is delivered to the trunk of his car. We develop construction and improvement heuristics for the VRPRDL based on two problem-specific techniques: (1) efficiently optimizing the delivery locations for a fixed customer delivery sequence and (2) efficiently switching a predecessor’s or successor’s delivery location during the insertion or deletion of a customer in a route. Furthermore, we conduct an extensive computation study to assess and quantify the benefits of trunk delivery in a variety of settings. The study reveals that a significant reduction in total distance travelled can be achieved, especially when trunk delivery is combined with traditional home delivery, which has both economic and environmental benefits.     

Real options and flexibility analysis in design and management of one-way mobility on-demand systems using decision rules

This study explores the concepts of real options and flexibility analysis as an approach to address uncertain demand growth in mobility on-demand (MoD) vehicle-sharing systems, with the goal of improving expected lifecycle performance. As MoD systems are gaining popularity worldwide, they inevitably face significant uncertainty in terms of needs and customer demands. Designing, planning capacity deployment, and operating such system can be challenging, and require significant capital investments for companies and cities. Two distinct real options analysis (ROA) models are developed to evaluate and optimize flexible strategies for these systems, relying on a novel methodological approach to value flexibility based on decision rules. The decision-rule-based approach differs from standard ROA approaches used to quantify the value of flexibility in irreversible investment projects, typically based on dynamic programming. It emulates the decision-making process by capturing mathematically a triggering mechanism that determines when it is best to exercise the flexibilities embedded in the system design. Two prevalent types of MoD systems are studied in this paper as demonstration of the methodological framework: a station-based system where customers must pick up and return the vehicle at specific locations, and a free-floating system, where customers may pick up and drop the car anywhere within a certain area. A simulation-based approach is used to analyze the station-based system, which models the rebalancing operations from a micro-level perspective. The approach consists of a discrete event simulator for performance estimation, and an optimization algorithm for design space exploration that integrates a population-based search algorithm with Optimal Computing Budget Allocation (OCBA). For the free-floating system, an analytical model is developed where the decision rule is formulated into and solved using stochastic mixed integer programming (MIP). The study provides guidance to system operators on potential strategies for deploying MoD systems, considering explicitly uncertainty and flexibility as a value enhancing mechanism.     

Vehicle scheduling under stochastic trip times: An approximate dynamic programming approach

Due to unexpected demand surge and supply disruptions, road traffic conditions could exhibit substantial uncertainty, which often makes bus travelers encounter start delays of service trips and substantially degrades the performance of an urban transit system. Meanwhile, rapid advances of information and communication technologies have presented tremendous opportunities for intelligently scheduling a bus fleet. With the full consideration of delay propagation effects, this paper is devoted to formulating the stochastic dynamic vehicle scheduling problem, which dynamically schedules an urban bus fleet to tackle the trip time stochasticity, reduce the delay and minimize the total costs of a transit system. To address the challenge of “curse of dimensionality”, we adopt an approximate dynamic programming approach (ADP) where the value function is approximated through a three-layer feed-forward neural network so that we are capable of stepping forward to make decisions and solving the Bellman’s equation through sequentially solving multiple mixed integer linear programs. Numerical examples based on the realistic operations dataset of bus lines in Beijing have demonstrated that the proposed neural-network-based ADP approach not only exhibits a good learning behavior but also significantly outperforms both myopic and static polices, especially when trip time stochasticity is high.     

Scheduling of airport runway operations using stochastic branch and bound methods

In this paper we present a solution methodology based on the stochastic branch and bound algorithm to find optimal, or close to optimal, solutions to the stochastic airport runway scheduling problem. The objective of the scheduling problem is to find a sequence of aircraft operations on one or several runways that minimizes the total makespan, given uncertain aircraft availability at the runway. Enhancements to the general stochastic branch and bound algorithm are proposed and we give the specific details pertaining to runway scheduling. We show how the algorithm can be terminated early with solutions that are close to optimal, and investigate the impact of the uncertainty level. The computational experiment indicates that the sequences obtained using the stochastic branch and bound algorithm have, on average, 5–7% shorter makespans than sequences obtained using deterministic sequencing models. In addition, the proposed algorithm is able to solve instances with 14 aircraft using less than 1 min of computation time.     

Adding a new station and a road link to a road–rail network in the presence of modal competition

In this paper we study the problem of locating a new station on an existing rail corridor and a new junction on an existing road network, and connecting them with a new road segment under a budget constraint. We consider three objective functions and the corresponding optimization problems, which are modeled by means of mixed integer non-linear programs. For small instances, the models can be solved directly by a standard solver. For large instances, an enumerative algorithm based on a discretization of the problem is proposed. Computational experiments show that the latter approach yields high quality solutions within short computing times.     

��������·��·����ά�޼ƻ��Ż�ģ��

制定铁路线路养护维修计划既要保证线路充分维修,又要兼顾经济效益.为此,以区域路网为研究对象,建立了基于整数规划的铁路线路养护维修计划优化模型.模型考虑了路网中线路之间维修资源的约束,以维修时间和股道占用状态为决策变量,以股道占用费用、维修费用及惩罚费用总和最小化为目标,通过集中安排线路中各项养护维修活动节省维修支出,减少维修活动对股道的占用时间进而达到优化目的.基于启发式算法设计了模型求解方法,仿真实验结果表明,模型具有较好的实用性,能够为编制铁路线路年度养护维修计划提供决策支持.