资源描述：
《局外k-卡车调度问题及其MCMF法求解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2005年5月系统工程理论与实践第5期 文章编号:100026788(2005)0520108205局外k2卡车调度问题及其MCMF法求解1,21马卫民,陈国青(11清华大学经济管理学院,北京100084;21西安工业学院经济管理学院,陕西西安710032)摘要:局内问题及其解法的研究是优化领域研究热点之一,而有关局内问题解法的研究必将涉及相应的局外问题.针对局外k2卡车调度问题,给出了如下研究结果:给出了一种通过构造加权有向图,进而应用最小费用最大流法(MinimalCostMaximalFlow,简记为MCMF)求解该问题的方法;给出了应用动态规划(DynamicProgramming,简
2、记为DP)以及MCMF求解该问题的算法复杂性并给予证明;通过一个具体的实例来说明MCMF求解的思路.关键词:局外k2卡车问题;MCMF法;算法复杂性中图分类号:TB11411文献标识码:AOff2lineSchedulingofk2TruckProblemandItsMCMFAlgorithm1,21MAWei2min,CHENGuo2qing(11SchoolofEconomicsandManagement,TsinghuaUniversity,Beijing100084,China;21SchoolofEconomicsandManagement,Xi’anInstituteofTechn
3、ology,Xi′an100032,China)Abstract:Inthefieldoftheoptimization,theresearchconcerningon2lineproblemanditssolutionsbecomesanattractiveresearchdirection.Whenwedosomeresearchontheon2lineproblemanditssolutions,theoff2lineproblemanditssolutionmustbeinvolved.Fortheoff2lineschedulingofk2truckproblem,someresul
4、tswereobtainedinthispaper:aMCMFalgorithm,whichisusedtosolvetheproblemafterconstructingaweighteddirectedgraph,ispresented;thecomplexitiesoftheDPandMCMFalgorithmsaregivenandproved;asimpleexampleisgiventoexplaintheMCMFalgorithm.Keywords:off2lineschedulingofk2trcuckproblem;MCMFalgorithm;complexityofalgo
5、rithm0 引言随着局内问题(on2lineproblem)的大量发现以及对局内问题的愈来愈广泛的研究,同时也提出了大量的相应的局外问题(off2lineproblem).局内问题研究是否存在一种算法,它在变化因素的每一个特例中都能[1～10]给出一个方案,使得由这一方案所得到的解离最优方案给出的解总在一定的比例范围之内.而最优方案给出的解则是相应的局外问题的解.卡车调度问题的实际背景是一个卡车货运公司如何调度卡车来完成顾客所提出的一个接一个的具体服务要求.对于一个卡车货运公司,假设它有k辆卡车在一个有限交通网络上进行载货服务;而且卡车每次载重相同,每个服务要求均由总调度台调度卡车来完成.考
6、虑如下两个问题:1)事先给定一个要求服务的任务序列,如何调动卡车使得相关的费用最少?2)如果服务要求是在服务过程中一个个地接到的,这样每一时刻只能知道在此之前的任务序列与服务过程,那么如何调动卡车费用较少呢?卡车调度问题的优化目标是所有卡车服务的总费用数最少.由于行驶相同距离的路程,重载与空载所花的费用是不相同的,所以卡车行驶的总路程与其所花的总费用并不成正比,从而总里程数不能作为我们的优化目标.为了研究问题的方便,假设单位路程重载与空载所花的费用之比为θ.这样,就可以用卡车空载的总里程数与重载总里程数的θ倍(θ≥1)的和作为优化目标.问题1)是个局外问题,而问题2)是一个收稿日期:20042
7、05214资助项目:由中国博士后科学基金(2003034014);国家自然科学基金(70401006、70231010)作者简介:马卫民,清华大学经济管理学院博士后,E2mail:mawm@em.tsinghua.edu.cn.©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.第5期局外k2卡车调度问题及其MCMF法求解1
