A two-phase heuristic approach to the bike repositioning problem

An approach to overcome the bike imbalance problem is to transfer excess bikes to branches with bike shortages. This study develops a constrained mathematical model to deal with a multi-vehicle bike-repositioning problem, and aims to minimize the sum of transportation and unmet demand costs over a planning horizon through bike-transfer strategies under a minimum service requirement. A two-phase heuristic based on linear programming was proposed to solve the problem and produce compromising solutions. In the first phase, the paper developed a linear programming model to quickly develop decisions related to bike inventory, unloading, and loading for all stations for each time slot. In the second phase, this paper proposed an iterative approach through two parameter sensitive mathematical models to sequentially reduce the problem scale to develop decisions related to bike transfers. Computational results show that the proposed approach is superior to a CPLEX optimizer and a hybrid heuristic based on a genetic algorithm. The proposed approach was used to analyze the bicycle system in Taiwan. The impacts of various system parameters on the system were also investigated.     

高峰期内的公交服务可靠度研究

在分析高峰期内道路交通现状和高峰客流特点的基础上,从可靠度理论的角度,对乘客在车内的拥挤成本、由于等车产生的时间延误惩罚成本等进行了分析,建立了高峰期内公共交通系统服务可靠度的模型,是评价公交服务能力的一种有效方法.     

A mathematical programming model for the bus deviation route problem

In small towns, or in those peripherical metropolitan areas in which the demand for public transportation is relatively low, the objectives of the bus route planner are different from those faced in highly congested networks. Some towns, also in Italy, are experimenting with urban public transportation systems where regular bus routes are designed which allow users located at specific points outside the main line to signal their presence to the bus driver, who then deviates from the main route to satisfy this demand. This way the bus line is a mixture between a regular line and a dial-a-ride system. The bus deviation route problem is concerned with the design problem which arises in planning the location of the demand points outside the line. A model is presented which takes into account both the advantage of passengers served by this deviation device and the disadvantage suffered by passengers on the bus, whose travel time increases during deviations, and by passengers downstream of the deviation whose waiting time also increases. Through some modeling assumption we are able to represent this problem as a mixed integer linear programming problem, whose relatively low dimension allows for exact solution through standard simplex-based branch and bound code. The proposed model has been applied to a real case and some results of this are presented and discussed.     

A model for setting services on auxiliary bus lines under congestion

In this paper, a mathematical programming model and a heuristically derived solution is described to assist with the efficient planning of services for a set of auxiliary bus lines (a bus-bridging system) during disruptions of metro and rapid transit lines. The model can be considered static and takes into account the average flows of passengers over a given period of time (i.e., the peak morning traffic hour). Auxiliary bus services must accommodate very high demand levels, and the model presented is able to take into account the operation of a bus-bridging system under congested conditions. A general analysis of the congestion in public transportation lines is presented, and the results are applied to the design of a bus-bridging system. A nonlinear integer mathematical programming model and a suitable approximation of this model are then formulated. This approximated model can be solved by a heuristic procedure that has been shown to be computationally viable. The output of the model is as follows: (a) the number of bus units to assign to each of the candidate lines of the bus-bridging system; (b) the routes to be followed by users passengers of each of the origin–destination pairs; (c) the operational conditions of the components of the bus-bridging system, including the passenger load of each of the line segments, the degree of saturation of the bus stops relative to their bus input flows, the bus service times at bus stops and the passenger waiting times at bus stops. The model is able to take into account bounds with regard to the maximum number of passengers waiting at bus stops and the space available at bus stops for the queueing of bus units. This paper demonstrates the applicability of the model with two realistic test cases: a railway corridor in Madrid and a metro line in Barcelona.     

A biased random-key genetic algorithm for road congestion minimization

One of the main goals in transportation planning is to achieve solutions for two classical problems, the traffic assignment and toll pricing problems. The traffic assignment problem aims to minimize total travel delay among all travelers. Based on data derived from the first problem, the toll pricing problem determines the set of tolls and corresponding tariffs that would collectively benefit all travelers and would lead to a user equilibrium solution. Obtaining high-quality solutions for this framework is a challenge for large networks. In this paper, we propose an approach to solve the two problems jointly, making use of a biased random-key genetic algorithm for the optimization of transportation network performance by strategically allocating tolls on some of the links of the road network. Since a transportation network may have thousands of intersections and hundreds of road segments, our algorithm takes advantage of mechanisms for speeding up shortest-path algorithms.     

Dynamic journeying under uncertainty

We introduce a journey planning problem in multi-modal transportation networks under uncertainty. The goal is to find a journey, possibly involving transfers between different transport services, from a given origin to a given destination within a specified time horizon. Due to uncertainty in travel times, the arrival times of transport services at public transport stops are modeled as random variables. If a transfer between two services is rendered unsuccessful, the commuter has to reconsider the remaining path to the destination. The problem is modeled as a Markov decision process in which states are defined as paths in the transport network. The main contribution is a backward induction method that generates an optimal policy for traversing the public transport network in terms of maximizing the probability of reaching the destination in time. By assuming history independence and independence of successful transfers between services we obtain approximate methods for the same problem. Analysis and numerical experiments suggest that while solving the path dependent model requires the enumeration of all paths from the origin to the destination, the proposed approximations may be useful for practical purposes due to their computational simplicity. In addition to on-time arrival probability, we show how travel and overdue costs can be taken into account, making the model applicable to freight transportation problems.     

基于线路“异质性”假设的轴辐式公共交通网络优化研究

特大城市公共交通局部静态拥堵问题日益成为制约公共交通网络运行效率提高的关键。针对这一问题改变线路“同质性”假设,在线路“异质性”假设的基础上,提出了将轴辐式网络设计运用到公共交通领域中来,综合考虑居民采用公共交通方式出行的单位运输可变成本、不变成本、枢纽换乘成本等要素,将枢纽间大型客车干线运输所带来的规模经济效应进行量化,构建了基于单分配、多枢纽、混合式网络结构特征的轴辐式公共交通网络优化模型,旨在多重约束下通过枢纽布局降低网络运输成本,提高公共交通网络站点的可达性。最后根据模拟退火算法对模型进行求解,并通过算例分析与讨论的方式验证了模型的有效性。     

军需物资调集规划问题的研究

以军需物资调集为背景 ,在系统分析的基础上建立了全局优化问题的数学规划模型 ,并对模型求解进行了研究 ,提出两阶段规划算法 .仿真计算结果表明所建模型的有效性     

周期列车运行图的多目标模型及基于Job-shop的遗传算法研究

计算机编制客运专线周期列车运行图问题已成为国内外研究的热点问题之一.在充分研究国内外周期与非周期列车运行图的规划理论与方法的基础上,构建了我国客运专线周期列车运行图的多目标模型,并将之转化为具有优先级结构的单目标模型;然后结合运行图的数学本质与周期性,设计了基于Job-shop的遗传算法,弥补了国外基于PESP理论所开发的周期列车运行图的算法不足.最后结合京津客运专线实例来验证算法的有效性.     

基于正交试验的乘用车运输网络优化方法

在交通部治理公路超限运输的背景下,本文研究了乘用车物流企业多式联运模式下的网络优化问题,以运输网络总成本最小为目标,考虑物流时效、枢纽节点容量及规模经济效应等因素,构建了基于轴辐式理论的运输网络优化模型,提出了混合智能优化算法。针对多参数多水平的寻优问题,对模型的三个关键输入参数,即枢纽节点数量、枢纽节点容量和规模效应折扣系数,引入正交试验方法,降低求解多参数多水平寻优问题的工作量,为确定各参数合理取值提供了新的途径。研究结果表明:枢纽节点容量、折扣系数与枢纽数量三个输入参数对优化结果的影响具有主次顺序,影响程度依次减弱,而且只有枢纽节点容量与折扣系数对乘用车运输网络总效益的影响起显著作用。采用混合轴辐式的网络结构与多式联运的运输组织模式进行优化后的运输网络,相对于原有“点对点”公路运输网络总成本减少10%,从运营管理与成本控制两方面均可有效应对公路治超带来的风险。     

公交网络时刻表再协同设计的多目标优化模型

为了改善公交服务质量,公交运营者试图调整现有时刻表的发车时间,使不同线路的车次协同到达换乘站点以方便乘客换乘。针对此场景,研究了公交时刻表重新协同设计问题,提出了求解该问题的多目标模型。模型考虑了对发车间隔灵敏的乘客需求、灵活的车次协同到站方式和发车时间的规则性,分析了该多目标模型的特征和计算复杂性,表明本文研究的问题是NP-hard问题,且它的帕累托最优前沿是非凸的,设计了基于非支配排序的遗传算法求解模型。算例表明,与枚举算法相比,提出的求解算法在较短的时间内可获得高质量的帕累托解。     

Hybrid large neighborhood search for the bus rapid transit route design problem

Due to an increasing demand for public transportation and intra-urban mobility, an efficient organization of public transportation has gained significant importance in the last decades. In this paper we present a model formulation for the bus rapid transit route design problem, given a fixed number of routes to be offered. The problem can be tackled using a decomposition strategy, where route design and the determination of frequencies and passenger flows will be dealt with separately. We propose a hybrid metaheuristic based on a combination of Large Neighborhood Search (LNS) and Linear Programming (LP). The algorithm as such is iterative. Decision upon the design of routes will be handled using LNS. The resulting passenger flows and frequencies will be determined by solving a LP. The solution obtained may then be used to guide the exploration of new route designs in the following iterations within LNS. Several problem specific operators are suggested and have been tested. The proposed algorithm compares extremely favorable and is able to obtain high quality solutions within short computational times.     

Service level robustness in stochastic production planning under random machine breakdowns

In this paper, we consider a multi-period, multi-product production planning problem where the production rate and the customer service level are random variables due to machine breakdowns. In order to determine robust production plans, constraints are introduced in the stochastic capacitated lot-sizing problem to ensure that a pre-specified customer service level is met with high probability. The probability of meeting a service level is evaluated by using the first passage time theory of a Wiener process to a boundary. A two-step optimization approach is proposed to solve the developed model. In the first step, the mean-value deterministic model is solved. Then, a method is proposed in the second step to improve the probability of meeting service level. The resulting approach has the advantage of not being a scenario-based one. It is shown that substantial improvements in service level robustness are often possible with minimal increases in expected cost.     

Pavement rehabilitation scheduling and toll pricing under different regulatory regimes

This paper addresses the highway pavement rehabilitation scheduling and toll pricing issues over a planning horizon. In the highway system concerned, two types of agents are considered, namely highway operator and road users. Two models, which account for different highway regulatory regimes (i.e. public and private), are proposed. In the public regulatory model, the government aims to maximize total discounted social welfare of the transportation system over the planning horizon by determining the optimal pavement rehabilitation schedule and toll level. In the private regulatory regime, a profit-driven private operator seeks to optimize the pavement rehabilitation schedule and toll level to maximize its own discounted net profit over the planning horizon. The proposed models treat the interactions between the highway operator and the road users in the system as a bi-level hierarchical problem in which the upper level is a multi-period pavement rehabilitation scheduling and toll pricing problem, while the lower level is a multi-period route choice equilibrium problem. A heuristic solution algorithm that combines a greedy approach and a sensitivity analysis based approach is developed to solve the proposed bi-level multi-period optimization models. An illustrative example is used to show the applications of the proposed models. The findings show that the highway regulatory regime, pavement deterioration parameter and the roughness-induced vehicle operating cost can significantly affect the pavement rehabilitation schedules and the toll level as well as the performance of transportation system in terms of total life-cycle travel demand, net profit and social welfare.     

A two-stage model for a day-ahead paratransit planning problem

We consider a dynamic planning problem for paratransit transportation. The focus is on a decision to take one day ahead: which requests to serve with own vehicles, and which requests to subcontract to taxis? We call this problem the day-ahead paratransit planning problem. The developed model is a non-standard two-stage integer recourse model. Both stages consist of two consecutive optimization problems: the clustering of requests into routes, and the assignment of these routes to vehicles. To solve this model, a genetic algorithm approach is used. Computational results are presented for randomly generated data sets.     

风险应对视角下不确定需求定位-路径鲁棒优化研究

及时准确地配送应急救援物资是突发公共事件救援过程中的关键环节,综合考虑应急救援过程中出现的需求随机性,路网的连通能力下降和设施点失灵等情况,采用车辆与直升机联合运输方式进行配送,以应急系统中各物资需求点的救援时间满意度之和最大、系统总成本最小及物资到达需求点的救援时间之和最小为目标,对多式联运三级网络应急物流系统定位—路径优化问题进行研究,建立了多目标定位—路径模型,并改进了遗传算法。最后,以汶川地震应急救援相关数据为例,对模型和算法的有效性进行了数据仿真验证,通过实验结果的对比分析,证明了鲁棒优化方法在处理不确定需求和设施失灵风险方面的有效性,进而为抵御突发公共事件发生后出现的风险,为解决突发公共事件发生后救援物资的安全及时准确配送提供了有效的方法。     

邮路规划与邮车调度最优化理论研究

对小规模MTSP问题,建立了可精确求解方案的0-1规划模型,并在满足邮政运输需求的前提下给出了最佳方案.问题一首先以县支局、县局为顶点构建无向赋权图,通过Floyd算法求解各局间的最短距离;然后以Fijk为决策变量,以邮车工作时间、车辆运载能力为主要约束,建立以总空载损失费用最小为目标的0-1非线性规划模型,运用规划软件Lingo求解.问题二考虑到市邮路成本,我们采用分层规划策略,首先以市支局、县局为顶点构建无向赋权图,求解出最短路矩阵,建立以邮路运行成本最小为目标的0-1非线性规划模型IIA求解;然后,建立各县区的最短路矩阵,同样建立规划模型IIB求解各县运输方案.问题三由于县局地理位置不变,对区邮路无影响,故以全市各县支局为中心采用逐步最优方法对所有县区支局重新划分;然后采用模型IIB求解.第四问中考虑县局迁移,我们建立近似的启发式算法完成县局选址,并运用规划模型II求解的到新方案.最后,我们对两种区域划分调整方法还进行了定量的分析.     

An integrated inventory–transportation system with modified periodic policy for multiple products

Efficient management of a distribution system requires an integrated approach towards various logistical functions. In particular, the fundamental areas of inventory control and transportation planning need to be closely coordinated. Our model deals with an inbound material-collection problem. An integrated inventory–transportation system is developed with a modified periodic-review inventory policy and a travelling-salesman component. This is a multi-item joint replenishment problem, in a stochastic setting, with simultaneous decisions made on inventory and transportation policies. We propose a heuristic decomposition method to solve the problem, minimizing the long-run total average costs (major- and minor-ordering, holding, backlogging, stopover and travel). The decomposition algorithm works by using separate calculations for inventory and routing decisions, and then coordinating them appropriately. A lower bound is constructed and computational experience is reported.     

基于实时公交信息的乘客乘车决策研究

实时交通信息的发布使乘客出行更具灵活性.调查乘客对实时公交系统的应用情况及功能需求,并提取乘客乘车决策规则.考虑乘客决策的"有限理性"特征构建决策模型:将乘车舒适性因素转换为时间成本,运用云模型建立定量时间到定性概念的映射;依据出行参考点确定出行方案的因素权重,建立期望效用函数;构建不同的出行场景,运用决策模型进行出行方案排序.结果表明:该模型能够更大限度地克服乘客理性限制对决策的影响,对多线路多因素方案下的乘客乘车行为做出决策,决策结果符合乘客决策规则,有助于为公交资源的规划与管理提供指导依据.     

Accessibility as the objective of public transportation planning: an integrated transportation and land use model

The subject of this paper is planning of public transportation in sparsely populated areas.The paper consists of four main parts. In part I an analysis of the system to be planned is carried out. A comparison with a survey on the traffic and transportation models available in the literature, though very voluminous, reveals a lack of a general model-framework for planning public transportation in sparsely populated areas. It is the aim of the present paper to fill this gap.Part II discusses how to evaluate optional plans for the physical and socio-economic structure of a region and concludes that this must be done by means of accessibility. Acessibility is defined in this paragraph.In part III a model is presented which describes the interdependance between on one hand the demand of accessibility of the population and on the other hand the transportation system, both public and private, and the location of facilities and residential areas. The applicability of some standard transportation and traffic models is discussed briefly in this section.Finally part IV describes a case study, in which the models set out in part III are applied. Some results are presented with conclusions.