The Downs-Thomson Paradox: Existence, Uniqueness and Stability of User Equilibria

Consider a network where two routes are available for users wishing to travel from a source to a destination. On one route (which could be viewed as private transport) service slows as traffic increases. On the other (which could be viewed as public transport) the service frequency increases with demand. The Downs-Thomson paradox occurs when improvements in service produce an overall decline in performance as user equilibria adjust. Using the model proposed by Calvert [10], with a ⋅|M|1 queue corresponding to the private transport route, and a bulk-service infinite server queue modelling the public transport route, we give a complete analysis of this system in the setting of probabilistic routing. We obtain the user equilibria (which are not always unique), and determine their stability.AMS subject classification: 60K30, 90B15, 90B20, 91A10, 91A13This revised version was published online in June 2005 with corrected coverdate     

Sensitivity Analysis Based Method for Optimal Road Network Pricing

Road pricing is an important economic measure for optimal management of transportation networks. The optimization objectives can be the total travel time or total cost incurred by all the travelers, or some other environmental objective such as minimum emission of dioxide, an so on. Suppose a certain toll is posed on some link on the network, this will give an impact on flows over the whole network and brings about a new equilibrium state. An equilibrium state is a state of traffic network at which no traveler could decrease the perceived travel cost by unilaterally changing the route. The aim of the toll setting is to achieve such an equilibrium state that a certain objective function is optimized. The problem can be formulated as a mathematical program with equilibrium constraints (MPEC). A key step for solving such a MPEC problem is the sensitivity analysis of traffic flows with respect to the change of link characteristics such as the toll prices. In this paper a sensitivity analysis based method is proposed for solving optimal road pricing problems.     

产销平衡运输问题的表上作业法解法的一个注记

本文给出了用表上作业法求解产销平衡运输问题当出现退化时在相应空格填“O”的更为明确的规则，利用该规则可以避免可能存在的多余计算。本文还给出了用改进后的表上作业法求解指派问题的方法和步骤，该方法与求解指派问题的常用方法“匈牙利法”相比，具有手工计算更为简便的优点。     

运输问题悖论及其研究

提出了运输问题的奇特现象——运输问题的悖论,讨论了运输问题悖论出现的条件,最后指出了研究运输问题悖论的现实意义.     

A simple greedy algorithm for a class of shuttle transportation problems

Greedy algorithms for combinatorial optimization problems are typically direct and efficient, but hard to prove optimality. The paper presents a special class of transportation problems where a supplier sends goods to a set of customers, returning to the source after each delivery. We show that these problems with different objective functions share a common structural property, and therefore a simple but powerful generic greedy algorithm yields optimal solutions for all of them.     

Smoothing method in multi-criteria transportation network equilibrium problem

ABSTRACT

This paper is aimed to study a single-product multi-criteria transportation network with capacity constraints. We use a vector version of the Heaviside Step function to construct an optimization problem, the solutions of which form the set of equilibria of our model. We propose two methods to solve this problem. The first one is based on a modified Frank-Wolfe gradient algorithm, and the second one is based on smoothing the objective function, the optimal solutions of which can be obtained by optimization tools. Numerical examples are also given to illustrate our approaches.     

Ein lösbarkeitskriterium für ein mehrstufen – mehrsorten – transportproblem

A variant for checking a solvability eriterion for multilevel multisort transportation problem is given.     

空铁联运网络的模型构建与算法设计

针对空铁联运网络具体联运路径的设计问题,借鉴枢纽航线网络p-枢纽中位问题的研究思想,将非枢纽城市间可以直航考虑进去,以联运网络总成本最低为目标函数,构建了允许直航的空铁联运网络混合整数规划模型,并设计了基于遍历搜索的最短路算法来求解模型.最后选取样本城市对模型和算法进行算例分析,给出了不同参数组合下的最优目标值和具体联运路径,设计了中国14个城市的空铁联运网络.算例结果表明联运总成本大小和联运路径的数目与枢纽数目m、折扣系数ρ紧密相关:m越大,ρ越小,联运总成本越小,联运路径数目越多;反之亦然.     

大跨越管道油气混输压力波速及响应特性研究

基于双流体模型,利用小扰动理论,提出了油气混输大跨越管道压力波速模型.利用计算机编程对其求解,通过大跨越管道油气混输实例,得到了以下结论:压力波速的变化受气相影响较大,即使少量气体也能在较大程度上影响压力波速,随混输气量增大,压力波速减小,压力响应时间延长;混输低点气体所承受的压力较混输高点大,从而低点处气相压缩系数小,混输低点较混输高点压力波速增大,压力响应时间相应缩短;在输运管道低点处,气体受到极大压缩,压力波速的变化不明显,几乎收敛于恒定值,在混输管道高点处压力波速变化剧烈.     

带有运输且加工具有灵活性的无等待流水作业排序问题

研究一类带有运输且加工具有灵活性的两阶段无等待流水作业排序问题, 其中每阶段只有一台机器, 每个工件有两道工序需要依次在两台机器上加工, 工件在两台机器上的加工及两道工序之间不允许等待. 给出两种近似算法, 并分别分析其最坏情况界. 第一种算法是排列排序, 证明了最坏情况界不超过5/2; 第二种算法将工件按照两道工序加工时间之和的递增顺序排序, 证明其最坏情况界不超过2. 最后, 通过数值模拟比较算法的性能. 对问题中各参数取不同值的情况, 分别生成若干个实例, 用算法得到的解与最优解的下界作比值, 通过分析这些比值的最大值、最小值和平均值来比较上述两个算法的性能.