An improved MIP heuristic for the intermodal hub location problem

Optimization methods have been commonly developed for the intermodal hub location problem because it has a broad range of practical applications. These methods include exact methods (limited on solving large-size problems) and heuristics (no guarantee on solution quality). In order to avoid their weakness but to leverage their strength, we develop an improved MIP heuristic combining branch-and-bound, Lagrangian relaxation, and linear programming relaxation. In the heuristic, we generate a population of initial feasible solutions using the branch-and-bound and Lagrangian relaxation methods and create a linear-relaxed solution using the linear programming relaxation method. We combine these feasible and linear-relaxed solutions to fix a portion of hub location variables so as to create a number of restricted hub location subproblems. We then combine the branch-and-bound method to solve these restricted subproblems for iteratively improving solution quality. We discuss in detail the application of the method to the intermodal hub location problem. The discussion is followed by extensive statistical analysis and computational tests, where the analysis shows statistical significance of solutions for guiding the heuristic search and comparisons with other methods indicate that the proposed approach is computationally tractable and is able to obtain competitive results.     

多模式交通条件下合理制定旅客票价的优化模型及算法

在本文中,充分考虑了旅客和交通管理部门两方面的利益,提出了一个双层规划模型来描述城市间多种交通方式竞争条件下合理制定旅客票价问题。在此模型中,既保障了旅客使自己的广义出行费用最小,又使得交通管理部门在客运市场的竞争中取得最大的经济效益。然后给出了求解该模型的基于灵敏度分析的启发式算法 (SAB)。最后用一个实际算例说明了该模型及算法的应用。     

Transportnetzgestaltung für Paketdienstleister

Zusammenfassung  In diesem Beitrag entwickeln wir ein Hub-Location-Modell zur Bestimmung der Standorte von Hubs aus einer gegebenen Menge von Depots. Mit einer stufenf?rmigen Transportkostenfunktion erhalten wir die effiziente Kombination von Fahrzeugen bestimmter Typen von einem oder mehreren Verkehrstr?gern. Ferner berücksichtigen wir direkte Transporte und die Regellaufzeit der einzelnen Transporte. In Anlehnung an ein vorhandenes Transportnetz eines Paketdienstleisters demonstrieren wir die Anwendbarkeit des Ansatzes.

---

Transportation network design for parcel service provider

Summary  In this paper we develop a hub location model to determine the locations of hubs from a given set of depots. Applying a stepwise transport cost function, we get the efficient combination of certain types of vehicles by one or more modes of transport. Furthermore, we consider direct transports and a maximum transit time. Based on an existing transportation network of a parcel service provider, the applicability of the model is shown.

     

合理制定铁路客票价格的优化模型及算法

在充分考虑出行者和铁路客运部门两方面的利益情况下 ,提出一个双层规划模型以得到在多种交通方式竞争条件下的铁路客票价格制定的最优策略 .既保障了出行者使自己的广义出行费用最小 ,又能使铁路客运部门在运输市场竞争中取得的经济效益最大 .并且给出了求解该模型的 SAB算法。最后用一个简单的算例说明了模型及算法的应用     

一种求解时变网络下多式联运最短路的算法

在运输过程中,往往不止有一种运输方式,可能同时有多种运输方式交叉,即可能多式联运的方式存在,不同的运输方式之间需要通过转运才可实现.同时,在运输过程中,成本、运输时间、风险等因素会随着时间的不同而变化.首先,将运输网络进行变形,然后给出了在时变网络条件下多式联运的最短路模型,设计了求解时变条件下多式联运的最短路的算法,利用此算法可以获得从起点到终点之间的最短路,并对算法的计算复杂性进行了分析.最后给出一个应用算例.     

竞争环境下的轴-辐式集装箱海运网络设计问题

针对航运企业的重组与全球扩张引起的竞争问题,提出了竞争环境下的轴-辐式集装箱海运网络设计模型。模型采用基于路径的变量作为决策变量,利用离散函数来表示航运企业与航运联盟的竞争可吸引的流量(或客户),目的在于通过设计混合轴-辐式集装箱海运网络,实现以更低的服务成本和更短的服务时间最大化可吸引的流量,建立了枢纽港口数量约束、航线连接约束、航线中转约束、流量竞争约束等,运用多点交叉遗传算法进行求解,最后结合亚欧航线的集装箱海运市场进行实例分析,对考虑客户需求多样性与航运联盟对策下的轴-辐式集装箱海运网络进行设计,并验证了算法的计算效果。     

A hybrid heuristic for the uncapacitated single allocation hub location problem

The uncapacitated single allocation hub location problem (USAHLP), with the hub-and-spoke network structure, is a decision problem in regard to the number of hubs and location–allocation. In a pure hub-and-spoke network, all hubs, which act as switching points for internodal flows, are interconnected and none of the non-hubs (i.e., spokes) are directly connected. The key factors for designing a successful hub-and-spoke network are to determine the optimal number of hubs, to properly locate hubs, and to allocate the non-hubs to the hubs. In this paper two approaches to determine the upper bound for the number of hubs along with a hybrid heuristic based on the simulated annealing method, tabu list, and improvement procedures are proposed to resolve the USAHLP. Computational experiences indicate that by applying the derived upper bound for the number of hubs the proposed heuristic is capable of obtaining optimal solutions for all small-scaled problems very efficiently. Computational results also demonstrate that the proposed hybrid heuristic outperforms a genetic algorithm and a simulated annealing method in solving USAHLP.     

碳交易政策下多式联运路径选择问题的鲁棒优化研究

针对碳交易政策下的多式联运路径选择问题,考虑运输时间和单位运费率不确定且其概率分布未知的情况,引入鲁棒优化建模方法对其进行研究。首先利用box不确定集合刻画分布未知的运输时间和运费率,然后在碳交易政策下确定模型的基础上,构建鲁棒性可调节的多式联运路径选择模型,并通过对偶转化得到相对易求解的鲁棒等价模型。实例分析表明,鲁棒模型能较好地处理参数概率分布未知的多式联运路径选择问题,方便决策者根据偏好调整不确定预算水平进行决策。运输时间和单位运费率的不确定性都会影响多式联运路径决策,但是作用机理有所不同。将上述碳交易政策下的模型拓展到其他低碳政策,结果表明多种低碳政策的组合能更好实现多式联运减排。     

禁忌搜索算法在单分配多枢纽轴辐式物流网络中的应用

随着经济的发展,轴辐式网络因有提高运输效率,优化资源配置,产生范围经济等作用越来越多的受到各方面学者的关注。本文对轴辐式网络进行优化分析,改进轴辐式网络的多重分配多枢纽中位问题模型,得到无容量限制的单分配多枢纽中位问题模型(USApHLP)的混合整数线性规划模型,并采用改进的禁忌搜索智能算法来求解,通过算例验证了禁忌搜索算法可以有效的求解单分配多枢纽中位问题。     

基于系统最优的城市公交专用道网络设计模型及算法

设置公交专用道是实现"公交优先"的重要手段,然而,专用道设置将改变不同交通方式的道路通行能力,进而影响交通网络的整体性能。本文试图提出一种基于系统最优思想的公交专用道网络设计方法,既保证出行者的利益,又能满足交通系统总费用最优的目标。首先,本文分析了公交专用道设置对公交车辆和社会车辆这两种交通方式道路通行能力的影响,基于经典的BPR函数,构造了考虑专用道设置的不同方式的路段阻抗函数。其次,分析了出行者在多方式交通网络中的模式选择和路径选择问题,采用用户平衡理论分析了城市多方式交通平衡配流问题,给出了相应的变分不等式模型。更进一步,采用双层规划方法构造了基于系统最优的城市公交专用道网络设计模型,该模型以交通网络总费用最小为优化目标,并考虑了不同交通方式的平衡流量约束,采用分支定界算法对该双层规划模型进行求解。最后,通过一个简单算例对模型及算法的可行性和有效性进行了分析和验证。     

A Model for the Transportation of Hazardous Waste*

Many decision problems, such as the transportation of hazardous waste, can be modeled by networks. However, due to the imprecise nature of much of the information decision makers have available, it is sometimes difficult to determine a best approach to the problem. To alleviate this problem, a network model that combines both precise and imprecise information is presented for the transportation of hazardous waste. The properties of the network model are investigated and solution procedures are presented.     

协同运输的路线整合问题研究

本文研究协同运输的路线整合问题(CTRIP):允许所有的O-D流(运输任务)在规定的路线长度内任意采取直通运输、单点中转、两点中转的整合运输路线,整合运输的中枢路段在支付固定成本后可产生运费折扣,如何选择O-D流的整合路线使得总成本最小? CTRIP广泛应用于航空、物流、快递等领域的整合运输实践。论文构造了CTRIP的混合整数规划模型和Benders分解算法,实验显示,算法表现出非常好的计算绩效。最后,我们利用一个具体实例对CTRIP与已有研究展开了比较,结论显示CTRIP更能保证中枢路段的规模优势 。     

Strategic and operational decision-making in expanding supply chains for LNG as a fuel

The European Union aims for a 40% reduction in greenhouse gas emissions by 2030, compared to 1990 levels, and recognizes the opportunities of Liquefied Natural Gas (LNG) as an alternative fuel for transportation to reach this goal. The lack of a mature supply chain for LNG as a fuel results in a need to invest in new (satellite) terminals, bunker barges and tanker trucks. This network design problem can be defined as a Two-Echelon Capacitated Location Routing Problem with Split Deliveries (2E-CLRPSP). An important feature of this problem is that direct deliveries are allowed from terminals, which makes the problem much harder to solve than the existing location routing literature suggests. In this paper, we improve the performance of a hybrid exact algorithm and apply our algorithm to a real-world network design problem related to the expansion of the European supply chain for LNG as a fuel. We show that satellite terminals and bunker barges become an interesting option when demand for LNG grows and occurs further away from the import terminal. In those situations, the large investments associated with LNG satellites and bunker barges are offset by reductions in operational costs of the LNG tanker trucks.     

Best routes selection in multimodal networks using multi-objective genetic algorithm

In this study, we propose a bi-level multi-objective Taguchi genetic algorithm for a multimodal routing problem with time windows. The mathematic model is constructed, which is featured by two optimal objectives, multiple available transportation manners and different demanded delivery times. After thoroughly analyzing the characteristics of the formulated model, a corresponding bi-level multi-objective Taguchi genetic algorithm is designed to find the Pareto-optimal front. At the upper level, a genetic multi-objective algorithm simultaneously searches the Pareto-optimal front and provides the most feasible routing path choices for the lower level. After generalizing the matrices of costs and time in a multimodal transportation network, the \(k\) -shortest path algorithm is applied to providing some potential feasible paths. A multi-objective genetic algorithm is proposed at the lower level to determine the local optimal combination of transportation manners for these potential feasible paths. To make the genetic algorithm more robust, sounder and faster, the Taguchi (orthogonal) experimental design method is adopted in generating the initial population and the crossover operator. The case study shows that the proposed algorithm can effectively find the Pareto-optimal front solutions and offer series of transportation routes with best combinations of transportation manners. The shipper can easily select the required shipping schemes with specified demands.     

Network Game and Capacity Investment Under Market Uncertainty

This paper investigates the impacts of competition and market uncertainty on airlines' network structures and capacity investment. The airlines choose their network structures and construct capacities while demands are unknown. After uncertainty is resolved, they determine the total number of seats to offer in each leg constrained by their capacities built earlier. We conclude that market uncertainty is the driving force of hub‐and‐spoke networks, whereas the market mean is the driving force of point‐to‐point networks. Which of the two countervailing forces dominates determines the equilibrium network structures. Moreover, we find that the airlines' total expected profits in the mixed equilibrium in which the airlines employ different networks are larger than in the pure hub‐and‐spoke network equilibrium in which each airline employs the hub‐and‐spoke network. However, the mixed equilibrium does not necessarily yield larger profits than the pure point‐to‐point equilibrium in which each airline employs the point‐to‐point network.     

A heuristic approach to long-haul freight transportation with multiple objective functions

This paper studies a long-haul freight transportation problem stimulated by a real-life application, whose underlying vehicle routing problem is a multi-objective one, where travel time and route cost are to be minimized together with the maximization of a transportation mean sharing index, related to the capability of the transportation system of generating economy scale solutions. In terms of constraints, besides vehicle capacity and time windows, transportation jobs have to obey additional constraints related to mandatory nodes (e.g., logistic platform nearest to the origin or the destination) and forbidden nodes (e.g., logistic platforms not compatible with the operations required). Based on the network definition, routes can be multimodal. To solve this problem, we propose a heuristic algorithm that can be applied in the tactical and the operational planning phase, and present the results of an extensive experimentation.     

Designing <Emphasis Type="Italic">k</Emphasis>-coverage schedules in wireless sensor networks

Some sensor network applications require k-coverage to ensure the quality of surveillance. Meanwhile, energy is another primary concern for sensor networks. In this paper, we investigate the Sensor Scheduling for k-Coverage (SSC) problem which requires to efficiently schedule the sensors, such that the monitored area can be k-covered throughout the whole network lifetime with the purpose of maximizing network lifetime. The SSC problem is NP-hard and we propose two heuristic algorithms under different scenarios. In addition, we develop a guideline for users to better design a sensor deployment plan to save energy by employing a density control scheme. Simulation results are presented to evaluate our proposed algorithms.     

随机多阶段分销网络设计模型

为了更合理的设计分销网络,本文提出了一种随机多阶段的联合选址-库存模型。在该模型中,不仅考虑了经济规模和分摊效益的影响。同时通过情景规划,考虑了在多阶段的分销网络设计中,对未来市场环境的不确定性。该模型的目标是使整个战略周期内的总期望成本(包括库存、运输、选址成本与损失的收益)最小。本文将该模型建立成为了一个非线性的整数规划模型,同时提出了一种基于拉格朗日松弛的求解算法。最后,本文使用该算法求解了三组不同规模的算例,得到的计算结果证明了拉格朗日算法是求解该模型的有效算法。     

A characterisation of logistics networks for product recovery

Recovery of used products is receiving much attention recently due to growing environmental concern. Efficient implementation requires appropriate logistics structures to be set up for the arising goods flow from users to producers. We investigate the design of such logistics networks. As a basis for our analysis we review recent case studies on logistics network design for product recovery in different industries. We identify general characteristics of product recovery networks and compare them with traditional logistics structures. Moreover, we derive a classification scheme for different types of recovery networks.     

Stochastic Measures of Network Resilience: Applications to Waterway Commodity Flows

Given the ubiquitous nature of infrastructure networks in today's society, there is a global need to understand, quantify, and plan for the resilience of these networks to disruptions. This work defines network resilience along dimensions of reliability, vulnerability, survivability, and recoverability, and quantifies network resilience as a function of component and network performance. The treatment of vulnerability and recoverability as random variables leads to stochastic measures of resilience, including time to total system restoration, time to full system service resilience, and time to a specific α% resilience. Ultimately, a means to optimize network resilience strategies is discussed, primarily through an adaption of the Copeland Score for nonparametric stochastic ranking. The measures of resilience and optimization techniques are applied to inland waterway networks, an important mode in the larger multimodal transportation network upon which we rely for the flow of commodities. We provide a case study analyzing and planning for the resilience of commodity flows along the Mississippi River Navigation System to illustrate the usefulness of the proposed metrics.