基于专用道设置的交通规划问题的建模与求解

摘要

随着全球经济一体化的飞速发展,诸如奥林匹克运动会,世界博览会等大型特殊事件越来越多的在世界各地举办。这些大型特殊事件有一个共同特点就是在举办期间有大量的人流进入事件的举办地,在短时间内给举办地的交通状况带来极大的压力。这些大型特殊事件的主办方已经意识到解决这类交通问题的重要性,并开始采取各种措施处理事件举办期间的交通问题。其中,为这些大型特殊事件的参与者设置临时的专用通道是一种有效的办法。然而,目前尚没有采用数学的方法对专用道设置问题进行过定量的分析求解。因此,本论文提出了一个新的优化问题“基于专用道设置的交通规划问题”。针对本论文提出的新的优化问题,作者建立了新的数学模型,就所提出的数学模型,开发了启发式算法,元启发式算法以及下界,并用海量的随机算例证明了算法的有效性。本论文的主要的工作在于:为了满足大型特殊事件的交通需求,通常要求主办方在规定时间内将指定人员或指定物品从指定地点运送到指定活动地点。作者提出了一个新的优化问题“基于专用道设置的交通规划问题”。这类问题是运筹学界尚未涉及的新的领域,可应用于所有大型特殊事件中的紧急交通状况。为交通运输问题开辟了一个新的研究方向,同时具有很强的实际意义。
　　 本论文为“基于专用道设置的交通规划问题”建立了能反映实际问题的数学模型,并将其线性化,从而为模型的求解奠定了基础。首先将本论文提出的问题转化为网络模型,然后根据问题的实际意义,提出了一种新的目标函数,即最小化设置专用通道的总成本。以运输任务的时间限制作为主要约束条件,建立了0-1线性整数规划模型,并证明该问题是一个NP-hard问题。
　　 作者对本论文提出的0-1线性整数规划模型,开发了三种新的启发式算法,并比较了三种启发式算法的计算效果。以网络密度和时间约束的不同,对小规模随机算例进行了分类,在不同的算例中,将计算效果最好的启发式算法与通过数学规划软件Cplex得到的最优解进行了比较。验证了启发式算法的计算精度,以及在计算时间上巨大的优势。并以2010年广州亚运会为例,详细介绍并分析了对于本论文提出问题的建模与启发式算法的求解过程。并根据求解结果,得到了实际的能满足运送时间要求的基于专用道设置的交通规划方案。
　　 “基于专用道设置的交通规划问题”是一种有时间约束的交通问题,求解该问题在计算上十分复杂。因此,对于较大规模算例,数学规划软件Cplex难以在可接受时间范围内得到最优解。作者对本论文提出的数序模型进行了下界研究,通过拉格朗日松弛法得到了一种有效的下界。在较大规模算例中,以本论文开发的下界作为评判标准,验证了启发式算法的计算结果,同时也验证了下界的精度和稳定性。
　　 以本论文开发的启发式算法作为初始可行解,提出了一种新的元启发式算法--禁忌搜索算法,对启发式算法得到的解进行进一步的优化,得到了更精确的近似最优解。并以数学规划软件Cplex得到的最优解作为评判标准,在更大规模随机算例中,验证了禁忌搜索算法的计算精度及在计算时间方面的巨大优势。从而完善了对本论文提出的数学模型的求解方法。