局外k出租车问题及其动态规划求法一.pdf

第 l6卷第 6期 系 统 】一 程 学 报 Vo1．16No 6 2001年 l2月 JOURNA1．OFSYSTEMSENGINEERING D∽ ，200l “； ∞ ∞ ∞ f 局外 k一出租车问题及其动态规划求法 马卫 民．徐青川 (西安交通大学管理学院，西安 7l0049) 摘要 ：局 内问题噩其解击的研究是忧化领域砰宄热点之一，而有关局 内问题解法的研究∞将涉噩相应 的局外 问题 提 出了局外 ^ 出租车调度 问题 ，培 出了问题 的动 志规划求解方法，并耸 出谊 问题 的一十具体算倒 同 时简要地介龆 了局外 卡车调度 问题的动态规划采解方法． 关键 词 ：局外 出租车间题 ；局外 仁车u】题 动态规划 中图分类号 ：TB114 】 文献标识码 A 丈章编 号2001 Off—lineschedulingofk-taxiproblem anditsdynamic programmingprocedureoptimalalgorithm MAWei—min．XU Qing-ehuan (SchoolManagementofXianJiaotongUniversity，Xian710049．China) Abstract：In thefieldoftheoptim ization·theresearchconcerningon-lineproblem anditssolu t[onsisanattractiveresearchdirection．W henwedosomeresearchontheonlineproblem andits ~lutions．theofflineproblem and itssolutionmustbeinvolved．Thispaperproposesoff—line ~hedulingof taxiproblem and offlineschedulingof truckproblem and givestheoptimal off—linealgorithms．which usethedynamicprogramming．concerning taxiand truck prob一 [era．Moreover，papergivesanexampletoillustratethealgorithms． K words：Mfline~hedulingof taxiproblem ；off—lineschedulingof^ treuekproblem；dy namicprogramm ing 0 引 言 应的局外同题的解． 出租车调度问题的实际背景是一个出租汽车 随着局内问题 (on—lineproblem)的大量发现 公司如何调度出租车来完成顾客所提 出的一个接 以及对局 内问题 的愈来愈广泛的研究 ．同时也提 一 个的具体服务要求 对于一个出租汽车公司，假 出 了大量 的相应 的局外问题 (off—lineproblem)． 设它有 辆出租车在一个有限交通网络上进行载 局内问题研究是否存在一种算法，它在变化因素 客服务 ；每个服务要求均 由总调度 台调度 出租车 的每一个特例 中都能给出一个方案．使得由这一 来完成．考虑如下两个问题 方案所得到的解离最优方案给出的懈总在 一定的 1。事先给定一个要求服务 的任务序列 ，如何 比例范围之 内 ．而最优方案给出的解就是相