Combining Geographic Information Systems for Transportation and Mixed Integer Linear Programming in Facility Location-Allocation Problems

In this study, we aimed to assess the solution quality for location-allocation problems from facilities generated by the software TransCAD®?, a Geographic Information System for Transportation (GIS-T). Such facilities were obtained after using two routines together: Facility Location and Transportation Problem, when compared with optimal solutions from exact mathematical models, based on Mixed Integer Linear Programming (MILP), developed externally for the GIS. The models were applied to three simulations: the first one proposes opening factories and customer allocation in the state of Sao Paulo, Brazil;the second involves a wholesaler and a study of location and allocation of distribution centres for retail customers;and the third one involves the location of day-care centers and allocation of demand (0 - 3 years old children). The results showed that when considering facility capacity, the MILP optimising model presents results up to 37% better than the GIS and proposes different locations to open new facilities.

Obtaining Optimal Solution by Using Very Good Non-Basic Feasible Solution of the Transportation and Linear Programming Problem

For the transportation problem, Sharma and Sharma [1] have given a very computationally efficient heuristic (runs in O(c*n2) time) to give very good dual solution to transportation problem. Sharma and Prasad [2] have given an efficient heuristic (complexity O(n3) procedure to give a very good primal solution (that is generally non-basic feasible solution) to transportation problem by using the very good dual solution given by Sharma and Sharma [2]. In this paper we use the solution given by Sharma and Prasad [2] to get a very good Basic Feasible Solution to transportation problem, so that network simplex (worst case complexity (O(n3*(log(n))) can be used to reach the optimal solution to transportation problem. In the second part of this paper, we give a simple heuristic procedure to get a very good BFS to linear programming problem from the solution given by Karmarkar [3] (that generally produces a very good non-basic feasible solution in polynomial time (O(n5.5)). We give a procedure to obtain a good BFS for LP by starting from the solution given by Karmarkar [3]. We note that this procedure (given here) is significantly different from the procedure given in [4].

Intermodal Terminal Localisation Using a Linear Programming Approach: The Case Study of Togo and West African Landlocked Countries

In this paper, four potential cities to host an intermodal terminal for containers flowing through the Togolese transport corridor are examined. The transport cost minimization through the corridor is the main objective. Consequently, the transport modes that offer the least cost to the transport supply chain are proposed. To attain this goal the paper aims to identify the optimal location for an intermodal terminal on the Togolese corridor, by using the mathematical linear programming model. For this, three transport scenarios are analyzed, the rail, the road, and the combination of these two transport modes to each of the landlocked countries (LLCs) capital cities of Burkina Faso, Mali and Niger. Data of the average transport cost per mode, the cargo demand of the LLCs, and the distances from origin to destinations are input in the LINGO software. Based on the optimization results, we find that among the preselected terminals, the city of Mango located at 550 km in the northern part of the country is the optimal host location for an intermodal terminal along the Togolese corridor. The results of this study may be helpful to transport policy makers in the quest of rendering better servicing to the landlocked countries.

A NEW MODEL AND SOLUTION FOR TRANSPORTATION PROBLEM

Transportation problem has many real world applications, it can be solved by linear programming model, but in most time the model exists more for less paradox, this paper considers the reasons for the paradox and search the way to eliminate the phenomenon. First this paper formulates a loose constrained linear programming model for the transportation problem, and gives the definition of the paradox which exists in it, some preliminary notions and one example is also given. Then it gives a table based algorithm for the loose constrained model, the steps of the algorithm and example will follow. The examples show that: (1) It is not a contradictory that transportation problem exists more for less paradox. (2) The loose constrained model is better used in practice for its less total cost. (3) The algorithm is easy to calculate, to study and highly speed to convergence. Finally, comparied with other ways it shows that the loose constrained model can thoroughly eliminate the paradox.

Optimization of Urban Rail Transportation in Emerging Countries Using Operational Research Techniques

Rail systems are gradually becoming the most desirable form of transit infrastructure around the world, partly because they are becoming more environmentally friendly compared with airplanes and automobiles. This paper examines the place of emerging countries in this move of implementing modern rail system that will eventually enhance the realization of a low-carbon society. Network model, transportation model and linear programming algorithms are used to model the present urban rail transport system in Nigeria, as an emerging country, in order to optimize it. Operational research methods, including simplex method and MODI, with the aids of computer software (excel solver and LIP solver) were adopted to solve the resulting models. The results showed that optimization of rail transport system will not only reduce carbon emission but also bring about economic development which is required for the eradication of prevalent poverty in these emerging countries.

A Transshipment Model of Seven-Up Bottling Company, Benin Plant, Nigeria

This research work seeks to model the distribution of 50 cl Pepsi soft drink as a transhipment problem. The transshipment problem is an extension of the traditional transportation problem which takes into account a multi-phase transport system in which the flows of goods and services are taken through an intermediate point (transhipment points) between the origin and the destination with varying objective functions. The main focus in this research was to obtain the minimum cost of transporting 10,000 crates of the product from the Benin plant (source) through deports (transshipment points) to the Sapele-Warri region (sinks) where the product is demanded. Data collected were analyzed using TORA Windows Version 2.00 software. The analysis shows that the minimum cost of transporting the product can be achieved if the product is shipped directly from the source to the sink. This forms that basis for the conclusions and recommendations of the research.

基于装卸顺序的中型机多航段协同配载优化

多航段、多经停的航空货运航班,飞行过程中需要合理控制飞机的重心(CG)位置,保持平衡状态,中转站装卸操作过程中需要避免额外装卸操作,减少时间和劳力浪费,因此,研究多航段航班的协同配载问题具有重要现实意义。根据航空器自身特点与集装器(ULD)装卸顺序,结合各航段飞机装载平衡与过站机场ULD装卸操作要求,通过协调分配各航段ULD和散货位置,建立了中型机联程航班多目标整数线性规划模型。模型考虑了ULD和散货的质量、体积及与舱位的匹配限制,航空器限重、舱位限重、舱位及区域累积限重、上下舱联合限重和CG位置的平衡限制,以及前后航段ULD和散货的连接性约束。根据造成中间机场额外装卸操作的2种原因,基于装卸顺序,提出装卸优化模型,通过ULD的舱内平移,优化了CG,减少了装卸次数。以B757-200F机型为例,在两装一卸、一装两卸和两装两卸3种场景下,采用商用求解器Gurobi,分别针对3种不同目标函数组合进行求解和分析对比。实验表明:所提模型可以有效协调过站货物的额外装卸次数,优化前后两航段的CG位置。

线性规划的历史与发展

本文介绍了线性规划的起源与发展过程,对比了丹齐格与坎托罗维奇各自在线性规划方面的贡献.

虚拟编组条件下城轨列车单元灵活运用方法

基于虚拟编组运输组织模式,本文考虑客流时间和空间特征与列车单元实时动态编组之间的耦合关系,协调不同运营方向列车之间的虚拟联挂和虚拟摘解操作,研究虚拟编组条件下城市轨道交通列车单元灵活运用问题。具体地,将列车单元数量分配和周转衔接作为主要决策变量,以极小化总乘客等待时间和系统运营成本为目标,考虑虚拟编组列车单元分配、列车单元周转和乘客分配等约束条件,构建可用CPLEX等软件直接求解的混合整数线性规划模型。最后,以某城市轨道交通线路为例设计数值实验以验证所提方法的有效性。实验结果表明:相较于固定编组(6编组)方案,本文方法可降低约32.8%的总乘客等待时间,同时降低20.9%的系统运营成本;相较于固定编组(8编组)方案,本文方法在仅增加0.3%的总乘客等待时间情况下,降低40.7%的系统运营成本。上述实验结果表明,虚拟编组技术在提升城市轨道交通效率方面的潜在优势,且具有一定的实用价值。

一种基于改进遗传算法的航空集装器多目标配载优化方法

航空运输是重要的交通运输方式之一,而航空集装器配载会影响飞机飞行安全和航空公司商业利益。针对此问题,本文建立以机体轴惯性矩最小和重心偏差最小为目标的航空集装器装载的混合整数线性规划模型的方法,通过改进遗传算法中的适应度函数、选择、交叉和变异等操作提高算法的求解能力。实验结果表明,改进的方法会使重心偏差低于0.05%MAC,惯性矩减小10%以上。

模糊环境下带有时间窗的多式联运路径优化

为了提高运输经济性、准时性和可靠性,在规划运输方式在途运输时间和节点中转时间模糊性的基础上,以运输费用最小为目标研究了带有时间窗的多式联运路径优化问题,构建了问题的模糊线性规划模型,分别采用模糊机会约束规划和模糊期望值规划对模型进行清晰化处理,得到其等价可解形式。研究表明,较模糊期望值规划,模糊机会约束规划能够更好地处理运输经济性和时间可靠性的矛盾,能够提供多种路径优化方案,满足客户对经济性和时间可靠性的不同需求。

基于均衡性和能力利用的高速铁路标杆车运行图编制方法研究

高速铁路标杆车的服务品质对于提高铁路客运产品的竞争力具有重要意义,在现场实际编图过程中,高速铁路标杆车须优先铺画,因此标杆车运行图的编制结果决定了整个列车运行图的框架。为了提高高速铁路标杆车的服务品质,考虑标杆车区间运行时分约束、交路接续时间约束等编图基本约束,结合标杆车始发时间约束、成组约束等特殊约束,基于事件活动网络构建以OD服务均衡性和能力利用为目标的整数线性规划模型。设计分阶段迭代求解算法框架,嵌套商业求解器进行求解,第1阶段为不考虑安全间隔时间约束的标杆车分组问题,以OD服务均衡性为目标进行求解;第2阶段以求解得到的标杆车分组为输入,增加安全间隔时间约束,以能力利用为目标进行求解。最后以京广高速铁路为案例,使用实际编图参数,运用优化求解器ILOG CPLEX进行求解,验证模型的有效性和可行性。实验结果表明:优化模型可以在较短时间内高效求解,与实际图对比,上下行OD服务均衡性分别提升38.2%和51.7%,能力损失降低50%,针对不同规模的算例,在200 s内均能得到最优解。针对不同交路接续时间,得出限制标杆车在北京西站的交路接续时间在45 min以内,不会对OD服务均衡性和能力利用造成较大影响。研究结果可为高速铁路标杆车运行图编制及优化提供参考。

基于鲁棒软时间窗和箱种代用的铁路集装箱空箱调运优化

传统的空箱调运问题多是研究箱种之间的彼此独立性,而忽略实际运输中箱种代用的情况,针对这一普遍现象,同时考虑需求站对集装箱空箱到达有时间窗约束,以及运输走行时间不确定性会对时间窗产生影响,建立了鲁棒软时间窗和箱种代用的集装箱空箱调运模型。首先,依据走行时间不确定性特点,建立鲁棒软时间窗模型;其次,通过等价变换和对偶变换,将鲁棒软时间窗模型转换为线性规划模型,简化了模型;最后,将集装箱调运模型转换为一般的整数线性规划模型,使模型更易于求解。研究结果表明,将箱种代用引入模型,有效地配置了空箱调运,提高了运输效率,降低了运输成本;对不确定走行时间p的个数进行灵敏度分析,结果表明箱种代用和不代用情况下p都存在一个较小的上界。

基于Bootstrap方法和灰色关联分析法的企业原材料订购方案与运输策略

基于企业生产经营的现实情况,文章使用Bootstrap及灰色关联分析等方法对企业过去的原材料订购情况、供应商供应情况和转运商运输情况的相关数据进行了处理,并对供应商的供货特征和转运商的运输损耗特征进行了量化分析。其中,建立并应用了一种评价供应商重要性的评估体系,在不同条件下给出了企业最优订购方案和运输方案,分析了企业如何通过技术改造来提高产能的潜力。

求解运输问题的一种算法

文章给出了运输问题的一种算法，该算法计算过程容易掌握。

考虑船舶油耗的集装箱班轮航线配船方案

班轮航线配船主要是解决多船型在多条航线上的合理配置问题,目的在于充分利用船队资源.首先,分析航行速度对船舶油耗产生的影响,然后,根据班轮多港口挂靠和集装箱转运的特点,建立以周计划内船队运营总成本最小为目标的混合整数规划模型.算例中通过对航行速度的灵敏性分析,呈现了船舶油耗和船队运营总成本之间的二律背反规律.随着船舶加速,虽然船队运营总成本递减,但是集装箱的转运成本和港口靠泊作业成本却呈现增加的趋势.其次,运用了轴辐式网络的特点,能够从46个港口中选择一半数量的中转港进行集中转运操作,具有规模经济优势.

非固定区段运用的双机牵引机车周转优化模型

对于不成对机车周转图,多基于固定的机车运转区段且为单机牵引进行研究,传统机车周转图的勾划方法难以适应非固定区段机车周转图编制的需求.机车的非固定区段运用有利于缩短机车周转时间,优化机车周转方案,对提高机车运用效率意义重大.本文在充分考虑部分双机牵引不成对机车周转图中可能出现的情况:到达单机牵引列车数与出发单机牵引列车数不同,到达双机牵引列车数与出发双机牵引列车数不同.综合分析铁路运输运营效益、列车运行图均衡性等具体要求,以机车在站停留时间、机车周转图均衡性、机车周转距离、机车运用数量等4个目标函数为求解目标的基础上,建立了机车周转图的01多目标规划模型,并给出求解的方法.最后以西宁西—西宁货区段进行实例验证,得出了对应的最少机车总消耗时间,最优附挂方案和机车周转图.

基于ITS的公共交通换乘等待时间最短调度问题研究

为使公共交通的换乘时间实现最佳衔接,先进的公共交通系统的高效率和优势得以体现,在对各国研究现状分析的基础上,研究了ITS实时提供公共交通信息的条件下,公共交通换乘等待时间最短调度问题。为了对公共交通换乘总等待时间最短目标下的公共汽车发车时刻表确定方法进行分析,应用运筹学理论,分别针对一个换乘点和多个换乘点的情况建立了线性规划模型,并用一个换乘点的算例验证了模型的可行性和有效性。结果表明:该方法能最大限度地减少乘客换乘总等待时间,尤其是对于发车间隔较大的公共交通方式间换乘的时间节约效果更为明显。

航线配船与船队规划模型及算法实现

为提高船舶资源优化配置研究的实用性,建立了以船队总营运利润最大为目标函数的航线配船与船队规划数学模型。该模型将船队短期调配使用与长期发展规划结合起来统筹分析研究,利用线性规划的单纯形算法进行求解分析,并通过应用实例对模型和求解的有效性进行了验证。基于计算机语言混合编程的方法,设计并开发了航线配船与船队规划决策系统。运行结果表明,该系统稳定可靠,辅助决策效果良好。

关于城市高速道路交通动态控制问题的研究

以开发城市高速道路交通智能化控制与管理系统为背景，提出可以对应于进口匝道流入交通需求和路网上交通状态实时变化，以及多路径条件下驾驶员选择路径行为影响的流入交通系统控制方法和模型。其控制模型不仅较以往的研究有根本性的改进，而且还针对交通流的非定常性（或非稳定性）变化，加入了主线交通流行驶速度约束模型，因此其成果不仅可以用于预防交通阻塞为目的的流入交通控制，还可以应用于轻微阻塞条件下的流入交通控制。由于笔者运用的是线性规划的方法，所以，具有计算便捷、可靠的优点。在文中，笔者通过简单的算例，讨论分析了动态控制方法的基本特征。