物流运筹方法与工具 教学配套课件 彭秀兰 毛磊 第六节工程路线问题.pdfVIP

《物流运筹方法与工具》电子教案 ____第七章 动态规划 - - - 工程线路问题在物流运筹中是一个著名的命题。某物流 - - - 中心（如火车站、邮政的EMS等）的一辆运输车辆，从中心出 - 节 六 第 发，通过若干个接货点一次且仅一次，最后仍回到中心，问 应如何选择行走路线，能使总的行程最短？ 现在把问题一般化。设有n个点（包括物流中心和接货 线 路 程 工 点），以1、2、…、n表示之（第1点是物流中心）。dij表示 从第i个点到j个点的距离。一辆送货车辆从点1出发到其它每 个点去一次且仅一次，然后回到点1。问如何选择行走的路 题 问 线，能使总的路程最短？这个问题属于组合最优化问题，当n 不太大时，利用动态规划方法求解是很方便的。 - - - - - - - - - 《物流运筹方法与工具》电子教案 ____第七章 动态规划 由于车辆行程是从点1开始的，设送货车辆走到点i，记 - - - N ={2,3,…,i-1,i+1,…,n}表示由点1到点i的中间点集 - i - - 合。S表示到达点i之前中途所经过的点的集合，则有 节 六 第 S∈N。 因此，可选取(i，S)作为描述过程的状态变量，决策为 由一个点走到另一个点，并定义最优值函数f (i，S)为从 线 路 程 工 k 点1开始经由k个中间城市的S集到i城的最短路线的距离， 则可写出动态规划的递推关系为