带转运中心的车辆组合运输问题的模型与算法

带转运中心的车辆组合运输问题的模型与算法 杨丰梅 ,肖辉君 () 北京化工大学理学院 ,北京 100029 摘要 : 主要研究两类带有转运中心的车辆组合运输问题. 一类是多期单产品的物流问题 ,一类是单期 多产品的物流问题. 建立了研究的两类物流系统的数学模型与算法 ,并通过算例对模型和算法进行了验 证. 主要应用动态规划方法 、结合两阶段法与分支定界法的混合算法 ,使程序运行效率和解的满意性都 得到很大提高. () 关键词 : 转运中心 ;车辆运输问题 VRP;动态规划算法 ;混合算法 中图分类号 : F22413 文献码 : A The Vehicle Routing Problems with Transshipment Points YANG Feng2mei ,XIAO Hui2jun ( ) College of Science ,Beijing University of Chemical Technology ,Beijing 100029 ,China Abstract : In this paper , we mainly talk about two kinds of the vehicle routing problems with transportation center. One is VRP of single product with a customer in many days. The other is VRP of many products with single customer in a day. We give the mathematical model and algorithms about these two problems. At the same time we use some numeric examples to certify our conclusion. The algorithm used in this paper is that dynamic programming algorithm and blending algorithm which is made up by two2phase method and the branch delimit law. The solution and the program both are better. Key words : transshipment points ; VRP ; dynamic programming algorithm ; multiple method 1 引言 () 物流系统中的车辆运输问题 VRP于 1959 年由 Dantzig 和 Ramser 以配送路径优化问题首次提出后 ,就 吸引了数学 、运筹学 、管理科学等各个领域的无数科学家的兴趣 ,这不仅因为它是一类求解较难的组合优 1 化问题 ,更重要的是因为它有很强的使用背景 ,可产生极其可观的经济效益. 在制造业的物流系统中 ,转 运中心起到连接上游与下游的作用. 它的存在 ,虽然使物流系统得以畅通 ,但由于运输环节的变化 ,可能导 致物流费用的增加 ,同时使运输调度更为复杂. 因此 ,需要对转运中心的设置和使用合理规划. 从大多数已发表的论文和著作中的研究成果来看 ,关于 VRP 方面的文献相当丰富 ,但涉及到多阶段 2 ,5 6 运输与车辆组合方面的文章却很少,带转运中心的车辆组合运输问题的研究更是少见. 这主要是鉴 7 ,8 于问题本身的 NP - hard 属性 ,难以在现存的优化方法中找出有效的精确求解方式. 在文献6 中 ,作者 提出了一类转运中心问题 ,并建立了混合整数线性规划模型 ,给出了一类相应的求解算法 ,但鉴于问题的 NP2hard 属性 ,最后只给出了满意解 ;本文在文献6 的基础上 ,通过引入路径选择控制变量 ,改进了问题的 数学模型和算法 ,应用动态规划方法 、结合两阶段法与分支定界法的混合算法 ,使程序运行效率 、解的满意 性都得到了进一步提高. 2 组合运输问题的数学模型 考虑带有转运中心的从供货点到分销点的多期单产品物流系统 ,运输过程中的车辆组合以及相关运 收稿日期 :2006211210 输安排与库存问题可用图 1 简示 ,其中三个节点 n, n, n分别代表供货点 ,分销点和转运中心. 供货点 1 2 3 n处提供某一种产品 ,它可以先将部分产品送往转运中心 , l是供货点到转运中心的往返路径. 分销点 1 1 n处可以直接从供货点进货 ,也可以经转运中心补货. r, r表示分销点取货的往返路径. 2 1 2 假设 n处完成运输任务的车辆包括自备车辆和雇用车辆. 这些自备 2 ( ) 车不但有最大容量限制 ,而且在每一期 此处指每天内 ,还有车辆最长运 行时间限制. 如果在某一期 ,总需求量超过了自备车辆的总运输能力 ,可以 雇佣其他的车辆进行运输 ,雇佣车辆的种类有限 ,但每种的数量不限. 因雇 图 1 ,所以不需考虑雇佣车辆路径选择问题. 佣车辆的费用按使用次数来计算 同时假定 n处有足够的供应能力 , n处有足够的库存能力 , n处不允许存在库存. 对于每一期 ,分销点 1 2 3 的需求量必须满足. 下面分析如何利用转运中心 ,安排给定期内的运输与库存 ,使得该物流系统的相关费 用最低. 首先介绍模型中将要涉及到的参数和变量 : ( I 代表自备车辆集合 ; J 是雇佣车种类的集合 ; P 为所考虑期间集合 ; R 是自备车可能的路径集合 包 ) 括 r和 r两条路径. 1 2 参数 v, i ?I 表示自备车 i 的最大容量限制 ; v, j ?J 表示 j 种雇佣车辆的最大容量限制 ; v表示从 ni j h 1 点运往 n点的车辆的最大容量限制 , c为该种车辆的运行费用 ; c, i ?I 为自备车 i 从路径 r 运行的费 3 h ir 用 ; c, j ?J 为 j 种车辆的一次雇佣费用 ; c为单件产品每天的库存费用 ; d为第 p 天的总需求量 ; t是沿 j s p r 路径 r 运行一次的时间 ; w 是自备车辆每天的最长运行时间限制 ; T 为期间数. 决策变量 N 代表自备车辆 i 在第 p 天沿路径 r 的运行次数 ; Q代表自备车辆 i 在第 p 天沿 r 路径的irp irp 总运输量 ; N是第 p 天所使用的 j 种雇佣车辆的数目 ; Q为第 p 天由 j 种雇佣车辆运输的总量 ; s为第 p jp p jp 天的库存总量. 控制项 X, Y,均为布尔变量 ,表示相应路径的选取与否. i i 于是 ,该物流系统的主要目标是最小化总费用 ,车辆运输安排问题的数学表达式为 : ( ) cN + cN ()N X+Pmin cY+cN+ cs, 1irir p h hp ir p i i 1 irj jp s p ? 2 2 1 1??????i ?I p ?P i ?I ? ? ?Jp ?Pp P j p P ? c1 , c+ cirirh 12 ()s. t . X= , 2 i 0 , el se () Y= 1 - X, 3i i () Q- vN ?0 , Π i ? I ; Π p ? P ; Π r ? R , 4irp i irp ()Q- vN?0 , Π j ?J ; Π p ? P , 5 jp j jp ()s+ Q+ Q- d- s= 0 , Π p ? P , 6p - 1 irp jp p p ???i ?I r ?R j ?J ()N t ?w , Π i ? I ; Π p ? P , 7 irp r ?r ?R ()Q- vN ?0 , Π p ? P , 8ir p h hp ?2 i ?I () s= s= 0 , s?0 , Π p ? P , 90 T p () Q?0 , Q?0 , Π i ? I ; Π r ? r ; Π j ?J ; Π p ? P , 10irp jp ()N 、N 和 N为正整数或零 , Π i ? I ; Π r ? R ; Π j ?J ; Π p ? P. 11 irp hp jp 上述目标函数由四项构成 ,第一项表示选择了路径 r的车辆的总的运输费用 ,第二项表示选择了路 1 () 径 r的车辆的总的运输费用 包括从 n到 n,再从 n到 n的所有的车辆的运输费用,第三项表示总需 2 1 3 3 2 求超出自备车辆最大容量限制时所需雇佣车辆的总费用 ,第四项为总库存费用. () () 约束条件 2表示当走 r路径费用比走 r路径少时 ,车辆选择从 r路径上通过 ;约束条件 3表示与1 2 1 () () () () 2相反的意思. 约束条件 4和 5是对自备车辆最大容量的限制 ;约束条件 6是对每期的库存与运输平 () () 衡的限制 ;约束条件 7是对自备车辆最长运行时间的限制 ;约束条件 8是对 n处无库存的限制 ; 最后 , 3 () () 约束条件 9到 11是对模型的技术限制. 3 算法描述 由上述数学模型的特点 ,首先选用动态规划算法 ,把复杂的多期混合整数规划模型 ,利用运输和库存 的前后联系分解为数个单期子模型进行求解. 应用动态规划算法分解模型. 在所考虑的期间内 ,用 u表示第 p 天运输到 n点的总量 ,则状态转移p 2 [ 4 ] ( ) s表示当库存量为 s p p 方程为 : s+ u- d= s. 对于第 p 天 ,用 f 时 ,从第一天到该天最低的累计费 ppp pp - 1 ( ) ( ) 用 ; cu代表运输 u件产品的最低费用 ; hs为 p 阶段开始时的库存费用. 于是 ,有以下迭代方 p p p p - 1 p - 1 程 : ( ) ( ) ( ) ( ) { cu+ hs+ f s} f s= min p p p - 1 p - 1 p - 1 p - 1 p p ( )u?Ds p p p ( ). P 11 s= s = 0 0 T [ 2 ] ( ) 在上述方程中 , Ds是第 p 天末的库存量为 s时 , u取值的集合 . 对于第 p 天 ,通过求解如下的 p p p p ( ) ( ) 混合整数线性规划子模型 P,可以得到 cu以及相应的运输安排. 12 p p 针对每个子模型 ,再对路径进行选择 ,这里 ,我们加入控制项 X, Y,以简化选择路径的计算. 子模型 i i 的求解 ,应用了两阶段法和部分分支定界法的混合算法 1 ,第一阶段寻找合适路径 ,第二阶段在相应路径 上进行车辆安排. 2 2 1 1?? i ?I j ?J N cNX+ + cN ()ir ir ir Y+ cN, 12 i h h i j j ( ) Pmin c ?12 ir?i I + c 1 , c? chirir21 ()s. t . X= , 13 i 0 , el se () Y= 1 - X, 14i i () Q- vN ?0 , Π i ? I ; Π r ? R , 15ir i ir ()Q- vN?0 , Π j ?J , 16 j j j ()Q+ Q= u, 17ir j p ???i ?I r ?R j ?J ()N t ?w , Π i ? I , 18 ir r ? r ?R ()Q- vN ?0 , 19irh h ?2 i ?I ()Q?0 , Q?0 , Π i ? I ; Π r ? R ; Π j ?J , 20 ir j () N、N 和 N为正整数或零 , Π i ? I ; Π r ? R ; Π j ?J , 21ir h j 上述模型中的参数含义 ,除了 u表示运输到 n点的产品总量 ,其余均可参见 212 节给出的定义. 子模p 2 ( ) 型 P的目标函数由三项构成 ,第一项和第二项分别表示自备车和雇佣车的运输费用 ,第三项 12 () () () 为从 n点到 n点车辆的运输费用. 约束 15和 16为车辆最大容量限制 ; 约束 17为运输量平衡限制 ; 1 3 () () 约束 18为车辆最长运行时间限制 ;约束条件 19是从 n点到 n点车辆的运输次数限制. 1 3 定义成本矩阵和运输量矩阵 :在子模型中 ,每个自备车 i 根据该车最长运行时间限制 ,确定其所有可 () 能的路线安排 包括重复路线,每种路线安排所需的运输成本和运输量 ,按照递增的关系 ,形成成本矩阵 CI 和运输量矩阵 VI . 车辆选择策略 :在运输量矩阵 VI 中 ,从其中的最大运输量开始 ,根据总需求量和车辆最大容量限制 , 以及控制项 X, Y进行最小化总费用而设定车辆和运输路径.i i 混合算法 1 的具体步骤如下 : 步骤 1 :计算成本矩阵 CI 和运输量矩阵 VI . 步骤 2 :如果当天的总需求量超过所有自备车辆的最大运输量的总和 ,则转到步骤 4 . 否则 ,根据车辆 选择策略 ,进行自备车的选择和安排. 步骤 3 :若前一天的总运输量大于当天的总需求量 ,即 ,有库存 s,则在第二天的总运输量中抛出掉前p 一天的库存 ,转步骤 5. 步骤 4 :先把所有自备车 i 的最大容量排满 ,然后考虑雇佣车 j 的容量和费用 ,确定雇佣车的选择. ( ) 步骤 5 :令 s= 0 ,运行动态规划模型 P,则最小解可以通过从最后一个期间到第一个期间的反推 T 11 得到. 至此 ,我们可以得到详细的自备车的运输路径和使用顺序 、次数 ,雇佣车的种类选择 ,以及较少的总运 输费用. 4 数值实验 假定计划期为 7 天 ,有 6 辆公司自备车 ,每个自备车都有不同的最大容量和运行成本 ,雇佣车共有 4 种. 表 1 给出了所需的参数. 表 1 参数 参数 数值 ()d 需求 d= 2000 d= 4000 d= 3500 d= 7500 d= 2500 d= 4000 d= 5000 1 2 3 4 5 6 7 i i i i i i 公司自备车 123456 v 100 200 250 350 400 500 i c400 660 740 940 1140 1320 ir1 c350 580 600 650 880 1060 ir2 jjjj雇佣车 1 2 3 4 v200 350 450 800j c100 1550 2000 3500 j t t = 7 t = 4基本参数 r r1 r2 v= 100 c= 100 w = 12 h h 注意 ,上述参数表中的数据 :需求 、自备车和雇佣车的各种数值都是随机产生的 ,所以算法所求出的解 的好坏有一定的普遍性 ,并不是该例所特有的属性. 表 2,表 4 列出了计算结果. [ 6 ] 表 2 原模型算法下的计算结果 c = 0167s 雇佣车数量 N 自备车安排 j( )N u s f s p d hppp p i, i, i, i, i 1 2000 0 4 2050 50 5800 2 3 4 5 6 i, i, i, i, i 2 4000 0 15 3950 0 17804 2 3 4 5 6 i, i, i, i, i 3 3500 0 15 4450 950 31574 2 3 4 5 6 i, i, i, i, i, i N= N= 1 4 7500 14 6550 0 54970 1 2 3 4 5 6j3 j4 i, i, i, i, i 5 2500 0 9 2550 50 62330 1 3 4 5 6 i, i, i, i, i 6 4000 0 15 3950 0 74330 2 3 4 5 6 i, i, i, i, i, i 7 5000 0 17 5000 0 90240 1 2 3 4 5 6 前面的算例中 ,每期的需求呈现无规律状态 ,如果我们将需求进行排序 ,计算结果如表 5,表 7. 通过上述的两个算例 ,发现在为期 7 天的运货过程中 ,改进算法的结果 ,除了第一天的成本稍微高以 外 ,均比原算法的成本低 ,而且总成本也远远低于原算法的成本 ,这 ,改进算法在多期的问题中有优秀 表现. 同时 ,比较货物需求量无规律和呈递增规律时的车辆路径安排以及总费用 ,发现与需求量呈无规律 分布相比 ,需求量呈递增趋势时的总费用有所增加的规律. 表 3 改进模型算法下的计算结果 c= 0167 s ( )NN usf s 雇佣车数量 p d 自备车安排 j h p p p p i, i, i1 2000 0 10 2000 0 61501 5 6 i, i, i, i, i, iN= 2 2 4000 18 4000 0 175701 2 3 4 5 6 j1 i, i, i, i, i, i3 3500 0 18 3600 100 288571 2 3 4 5 6 i, i, i, i, i, iN= 19 4 7500 18 7400 0 419771 2 3 4 5 6 j1 i, i, i5 2500 0 13 2500 0 481274 5 6 i, i, i, i, i, iN= 2 6 4000 18 4000 0 595471 2 3 4 5 6 j1 i, i, i, i, i, iN= 7 7 5000 18 5000 0 714671 2 3 4 5 6 j1 表 4 自备车 i 的详细安排 自备车安排 相应的路径以及使用次数 p d i, i, i 每辆车均走一次路径 r以及一次路径 r1 2000 1 5 61 2 i, i, i, i, i, i 每辆车均走一次路径 r以及一次路径 r2 4000 1 2 3 4 5 61 2 i, i, i, i, i, i 每辆车均走一次路径 r以及一次路径 r3 3500 1 2 3 4 5 61 2 i, i, i, i, i, i 每辆车均走一次路径 r以及一次路径 r4 7500 1 2 3 4 5 61 2 i, i, i 每辆车均走一次路径 r以及一次路径 r5 2500 4 5 61 2 i, i, i, i, i, i 每辆车均走一次路径 r以及一次路径 r6 4000 1 2 3 4 5 61 2 i, i, i, i, i, i 每辆车均走一次路径 r以及一次路径 r7 5000 1 2 3 4 5 61 2 [ 6 ] 表 5 原模型算法下的计算结果 c= 0167s 雇佣车数量 N 自备车安排 j( )N u s f s p d hppp p i, i, i, i 1 2000 0 4 2200 50 5680 3 4 5 6 i, i, i, i 2 2500 0 9 2700 0 13440 3 4 5 6 i, i, i, i, i 3 3500 0 13 3300 200 23270 2 3 4 5 6 i, i, i, i, i 4 4000 0 15 4050 0 35624 2 3 4 5 6 i, i, i, i 5 4000 0 13 3950 50 47627 3 4 5 6 i, i, i, i, i 6 5000 0 15 5000 0 63537 2 3 4 5 6 i, i, i, i, i, i N= 3 7 7500 18 7500 0 90357 1 2 3 4 5 6j4 表 6 改进模型算法下的计算结果 c= 0167s 雇佣车数量 N 自备车安排 j( )N u s f s p d hppp p i, i, i 1 2000 0 10 2000 0 6150 1 5 6 i, i, i 2 2500 0 18 2500 0 13440 4 5 6 i, i, i, i, i, i 3 3500 0 18 3600 100 23587 1 2 3 4 5 6 i, i, i, i, i, i N= 2 4 4000 18 3900 0 35707 1 2 3 4 5 6j1 i, i, i, i, i, i N= 2 5 4000 13 4000 0 47127 1 2 3 4 5 6j1 i, i, i, i, i, i N= 7 6 5000 18 5000 0 59047 1 2 3 4 5 6j1 i, i, i, i, i, i N= 20 7 7500 18 7500 0 72217 1 2 3 4 5 6j1 表 7 自备车 i 的详细安排 p d 自备车安排 相应的路径以及使用次数 i, i, i每辆车均走一次路径 r以及一次路径 r 1 2000 1 5 6 1 2 i, i, i每辆车均走一次路径 r以及一次路径 r 2 2500 4 5 6 1 2 i, i, i, i, i, i每辆车均走一次路径 r以及一次路径 r 3 3500 1 2 3 4 5 6 1 2 i, i, i, i, i, i每辆车均走一次路径 r以及一次路径 r 4 4000 1 2 3 4 5 6 1 2 i, i, i, i, i, i每辆车均走一次路径 r以及一次路径 r 5 4000 1 2 3 4 5 6 1 2 i, i, i, i, i, i每辆车均走一次路径 r以及一次路径 r 6 5000 1 2 3 4 5 6 1 2 i, i, i, i, i, i每辆车均走一次路径 r以及一次路径 r7 7500 1 2 3 4 5 6 1 2 5 单期多产品运输问题 扩展上述多期单产品物流系统 ,可以首先考虑带有转运中心的从供货 分销点的单期多产品物流系统 ,如图 2 简示. 与图 1 区别的是供应点 点到 根据客户需求生产多种产品 : m, , m. 在这里 ,我们需要考虑两个问题 , 1 k 即装车策略 ,以及配送路线安排问题. 延用第二节的数学符号 ,新定义的符号说明如下 : 图 2K 是商品种类的集合. d 为总需求量 , m为第 k 种商品的总需求量 , p k k k 种商品的单位体积 , g是第 k 种商品的单位重量 ; m为第 k 种商品在第 i 辆车上的总运输量. 为第 k ik 决策变量 N 代表自备车辆 i 沿路径 r 的运行次数 ; Q代表自备车辆 i 沿 r 路径的总运输量 ; N是所 ir ir j 使用的 j 种雇佣车辆的数目 ; Q为由 j 种雇佣车辆运输的总量 ; s 为库存总量. j 因此 ,单期多产品运输问题的数学模型类似地可以表示为 : ? 2 2 1 1?i ?I i ?I j ?J N cN X+ + cN ir ir ir ()Y+ cN+ cs , 22 i h h i j j s ( ) Pmin C 2 ir? + c 1 , c? chirir21 ()s. t . X= , 23 i 0 , el se () Y= 1 - X, 24i i () pm? P, Π i ? I ; Π k ? K , 25k ik i () gm? v, Π i ? I ; Π k ? K , 26k ik i () Q- vN ?0 , Π i ? I ; Π r ? R , 27ir i ir ()Q- vN?0 , Π j ?J , 28 j j j ()Q+ Q- d - s = 0 , 29ir j ???i ?i r ?R j ?J ()N t?w , Π i ? I , 30 ir r ? r ?R ()Q- vN ?0 , 31irh h ?2 i ?I () s= s = 0 , 320 T () Q?0 , Q?0 , Π i ? I ; Π r ? R ; Π j ?J , 33ir j ()N 、N 和 N为正整数或零 , Π i ? I ; Π r ? R ; Π j ?J . 34 ir h j 借鉴第 3 节中的部分算法 ,我们了由分支定界法、两阶段法以及装车策略结合而成的混合算法 , 与原始算法的比较 ,可以得到该算法的解一定是任意初始解基础上迭代而成的更优可行解.装车策略 :是从运输量矩阵 VI 中的最大运输量所代表的自备车开始 ,将所有货物的总体积和总重量 () 中所需车辆数 预估比较多的项作为装车时的第一 ,则另一项为第二标准 ;若货物同时符合前一辆车 的第一标准和第二标准的最大限制 ,则货物进车 ;若货物符合第一标准 ,不符合第二标准 ,则考虑下一个货 物 ,反之 ,进入下一辆车的装车过程. 在该混合算法中 ,使用了第 3 节混合算法的车辆选择策略以及货物超出自备车总量时的雇佣车选择 方法 ,结合这里的装车策略 ,就可以得到单期多产品运输问题的车辆优化组合以及较小的总费用. 下述数值实验显示 ,该算法可得较优的货物装车安排 、车辆运输安排 ,节约了总费用 ,即保证在运输过 程中 ,按照合理满意的方式安排货物和车辆. 与传统的先进先出 ,或者后进先出等策略比较 ,我们的算法优 于传统算法 ,得到的是可以在实际中令客户满意的改进优化解 ,验证了算法的实用性. (() ) 算例中所需车辆参数 表 8随机产生 ;货物参数 表 9均为实际货物 ,通过调查产生 ,需求量也是一定 时间内的统计数据 ,所以关于货物的装车策略有一定的实际背景 ,对于实际应用有指导意义. 表 8 车辆参数 参数 公司数值 自备车 v iii 34iiii 1256250 350 100 200 400 500 P 1. 5 2 2. 5 3 3. 5 4 i 400 660 740 940 1140 1320 c ir1 c350 580 600 650 880 1060 ir2 j j j j 雇佣车1234 v 200 350 450 800 j c100 1550 2000 3500 j 其他参数 t t = 7 t = 4 r r1 r2 v= 100 c= 100 w = 12 h h 表 9 货物参数 经计算 ,总运输费用为 3400 ,结果如表 10 和表 11 . 由上述数据 ,根据每种货物的体积 、重量 ,以及自备 商品编号 单位体积 单位重量 总需求量 车的最大容量和体积的限制 ,我们给出此算例满意的装 m 0. 043. 75161车策略 ,可使用较少的车装所有的货物. 这里 , 自备车 m 0. 0722. 54272 i装载货物 m, m, m, m, 自备车 i装载货物 m,m 6 1 2 3 8 5 4 0. 036. 5303 m,自备车 i装载货物 m, m. 6 4 5 7 m 0. 06810254 对于相同算例 ,已有研究者使用 3 辆车 ,每辆最大 m 0. 0257. 2295 容积为 3 ,最大载重量为 1000 ,而本文的车明显最大载 m 0. 089126 重量较小. 所以 ,本算法节省了车辆载重 ,即节约了总成 m 0. 261. 277 本. m 0. 021068 表 10 装车策略结果 车辆 m m m m m m m m 12345678 i 000000001 i 000000002 i 000000003 i 000010104 i 000101005 i 111000016 () 表 11 自备车详细路径安排以及装货统计 这里 ,仅使用了自备车 i, i, i4 5 6 车量 最大载重 最大容积 实际载重 实际容积 运货安排 具体路径 编号 限制 限制 i m, m, m, m 使用一次路径 r500 383. 58 4 3. 604 61 2 3 81 i m, m 使用一次路径 r400 358 3. 5 2. 66 54 61 i m, m 使用一次路径 r350 217. 2 3 2. 545 45 71 6 结论与展望 本文主要研究了多期单产品问题和单期多产品问题. 前者首先采用动态规划算法进行模型分解 ,对子 模型的求解过程应用了由两阶段法和分支定界法改进的混合算法. 后者在前者的基础上 ,从单一的车辆组 合问题扩展到装车策略结合车辆运输安排两个问题的联合求解 ,并且根据问题本身的特性 ,给出了详细算 法. 通过以上的研究 ,以及算例比较可看出 ,改进算法确实可以得到比原始算法更令人满意的解 ,同时简化 了计算复杂性 ,算法的简便和易操作性为实现应用提供了可能. 因而 ,可以很好的服务物流公司 ,具有良好 的应用背景. 我们研究的带有转运中心的运输问题不是一个孤立的问题 ,它是由实际问题抽象简化而来的一系列 物流系统问题. 不仅仅涉及点 ,期间的问题 ,还有诸多现实因素可以考虑其中 ,诸如可继续推广至多期多商 品以及多点的物流系统等. 参考文献 : 1 赵冰洁. 配送中心配送优化研究D . 学位论文 , 西南交通大学 ,2004. Zhao B J . Distribution center and research of optimizing distribution project D . Chengdu : Southwest Jiaotong University ,2004. 2 Zhao Q H , Wang S Y. Dynamic multi2period transportation model for vehicle composition with transshipment points J . AMO 2 () Advanced Modeling and Optimization , 2001 , 31. () 3 Etezadi T , Beasley J E. Vehicle fleet composition J . Journal of the Operational Research Society , 1983 , 34 1:87 - 91. 4 Denardo E V , Rothblum U G , Swersey A J . A transportation problem in which costs depend on the order of arrival J . Management () Science , 1988 , 34 6:774 - 783. 5 Liu F H ,Shen S Y. The fleet size and mix vehicle routing problem with time windows J . Journal of the Operational Research Society ,1999 ,50 :721 - 732. 6 赵秋红. 几类物流优化模型的研究D . 学位论文 . 北京航空航天大学 ,2003. Zhao Q H. Research of several logistics optimization mode D . Beijing :Beihang University ,2002. 7 邢文训 , 谢金星. 现代优化计算算法M . 清华大学出版社 ,1999. Xing W X ,Xie J X. Modern Coptimization AlgorithmM . Beijing : Tsinghua University Press ,1999. 8 张之 , 李建德. 动态规划及其应用 M . 国防工业出版社 ,1994. Zhang Z Y ,Li J D. Dynamic Programming and ApplicationsM . Beijing :National Defense Industry Press ,1994. () 上接第 27 页 10 Hammer P L , Rosenberg I. On equivalent forms of pseudo2boolean programs. Applications of Theory to Numerical Analysis C . New York : Academic Press , 1972. 453 - 463. 11 Rosenberg I. Reduction of bivalent maximization to the quadratic case J . Research Operation , 1975 , 17. 12 Watters L J . Reduction of integer polynomial problems to zero2one linear programming problems J . Operations Research , 1981 , () 15 6: 1171 - 1174. 13 Hammer P L ,Rudeanu S. Pseudo2boolean programming J . Operations Research , 1969 , 17 : 233 - 261. () 14 Taha H A. A balasian2based algorithm for zero2one polynomial programming J . Management Science , 1972 , 18 6: 328 - 343. () 15 Taha H A. Further improvements in the polynomial zero2one algorithm J . Management Science , 1972 , 19 2: 226 - 227. () 16 Balas E. An additive algorithm for solving linear programs with zero2one variables J . Operations Research , 1965 , 13 4: 517 - 546. 17 Li D. Zero duality gap in integer programming : p2norm surrogate constraint method J . Operations Research Letters , 1999 , 25 () 2: 89 - 96. 18 Geoffrion A. Integer programming by implicit enumeration and Balas’method J . SIAM Review , 1967 , 9 : 178 - 190.19 Li D ,Sun X L . Nonlinear Integer Programming M . New York : Springer , 2006. () 20 胡运权. 运筹学教程 第二版M . 北京 :清华大学出版社 , 2002.