带时间限制的最小费用运输问题的求解方法

《带时间限制的最小费用运输问题的求解方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第20卷第6期2011年12月运筹与管理OPERATIONSRESEARCHANDMANAGEMENTSCIENCEV01．20．No．6Dec．201l带时间限制的最小费用运输问题的求解方法李珍萍1，徐清云2，栗娜2，马圆圆2(1．北京物资学院研究生部。北京lO“49；2．北京物资学院信息学院。北京101149)摘要：本文研究了带时间限制的最小费用运输问题。首先分析了运输量与运输时间的关系，并把运输时间划分成两部分，一部分与运输量无关，一部分与运输量有关；进一步根据运输时间与运输最的关系，把带时间限制的最小费用运输问题转化为变量有

2、上界的运输问题，给出了求解该问题的有效算法，并通过实例进行了计算。关键词：运筹学，模型与算法，带时间约柬，运输问题，最小费用中图分类号：022l文章标识码：A文章编号：l007—322l(2011)06—0009-06AMelhOdfOrSOIv-ngtheMinimumCO吼TranSpOrlatiOnPrOblemwithT．meUmitedLIZhen．pin91，XUQing．yun2，(1．Sc矗ool矿坳肌口tfon，&彬增阮f‰f鲫j渺，曰e洳略阮f踟f睨砧灯，曰e访增10l149，C^inn)LINa2，MAYuan

3、．yuan2101149，C^讥口；2．Dep口疗mem矿Gmdl‘口鲤，Be弧昭AbStract：Theminimumcosttran8portationproblemwithtimelimitedisinvestigatedinthispaper．Fi璐tly，therelation8hipbetweenthetmnsportationtimeandthetransport8tionqualitityi8analyzed，thentIletransport8tiontimeisdividedintotwopart8：onepar

4、thasnorelation8hipwiththetransportationqualitity；theotherpartisafunctionofthet豫nsportationqualitity．Furthe砷oM，accordingtothereJationshipbetweenthetransponationtimeondthetran8portationqualitity，theminimumc08ttransponationproblemi8refo珊ulatedintoatransportationproblemwit

5、hupperboundofvariables．AneffectsolVingmethodi8proposed，andsomenumercialexamplesareusedforsimulation．There8ultsshowthatthemethodofthispaperisefhcientfor80lvingthiskindofproblem．KeywordS：operationsresearch；modelandalgorithm；time“mited；transportationproblem；theminumumcost

6、0引言通常运输问题考虑的目标可以分为两类：一类是成本，即如何调运才能使运输成本最小，也就是通常所说的运输问题⋯；另一类是时间，即如何安排调运才能在最短的时间内完成任务，如最短时限运输问题¨’3】。在现实中的运输问题有时需要同时考虑成本和时间两个因素，寻求最佳运输方案。如要求在一定的时间内完成运输任务，并且总运输成本最小；或者在一定的运输成本限制下完成任务，并且所用时间最短。前者称为带时间限制的最小费用运输问题，后者称为带费用限制的最短时限运输问题。对于带时间限制的最小费用运输问题，虽然文献中已经有一部分研究成果¨。。，但这些研究都是

7、基于运输时间与收稿日期：20lO-07-28基金项目：北京市自然科学基金费助项目(1092011)；北京市属市管高等学校人才强教计划项目(PHR20l006217)；北京市教育委员会科研基地建设资助项目(wYJD200902)作者简介：李珍萍(1966-)．女．山东平度人．博士后．教授．硕士生导师，研究方向为运筹学理论及应用．物流工程；徐清云(1987-)．男，福建人．硕士研充生．研究方向为物流工程；采娜(1988-)。女．山东人。硕士研究生．研宽方向为物漉工程；马团圆(1988-)．女．山东人，硕士研究生，研究方向为物流工程。lO

8、运筹与管理2011年第20卷运输量无关这一前提的，他们认为第￡个产地到第．『个销地的运输时间可以表示成：f：=兰+二旦，其中u。。“j"矿表示产地A；的货物装卸速度，d。表示从A。到日，的距离，tJ口表示从A；到曰f空车行驶速度。显然