配送运输问题的模型与优化方法

《配送运输问题的模型与优化方法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2007年6月阴山学刊Jun.2007第21卷第2期YINSHANACADEMICJOURNALVo1.21No.2配送运输问题的模型与优化方法麻桂英（包头师范学院数学科学学院，内蒙古包头014030）摘要：本文主要运用供应链管理过程中出现的最小时差，讨论某物流公司在配送过程中，如何高效地满足供应商和客户对时间的不同要求，以此来建立时间约束模型，解决调度中的问题，并借助MATLAB对模型进行了计算和验证。关键词：配送；时间约束；MATLAB中图分类号：O224文献标识码：A文章编号：1004-1869(2007)

2、02－0018－031最小时差以同时开始）。设工程由n>0个不可中断的实际活动构成，除min此而外，引入虚活动0和n+1，表示工程的开始和结定义2:若没有实际活动h具有最小时差，dhi则称活动i为初始活动。实际活动i称为终止活动，是束。活动0，1，2,…，n+1分别用网络节点0，1，2，min指无实活动j使得最小时差为。d…，n+1表示，这样V={0,1,2,…,n+1}是网络的节点ij为了保证活动0和n+1代表开始与终止，设立下集。设Pi为i的处理时间,其中P0=Pn+1=0，Pi∈N，进面约定：而，设Si≥0

3、为活动i的开始时间，其中虚活动0，n+1对工程的每个初始活动i，假定最小时差已知minmin的开始时间分别是S0:=0,Sn+1:=T，T为工程周期。d0i≥0，若d0i=0，则在工程开始时活动i可以开dmin始。定义1:对两个活动i，j，给出时差ij∈Z≥0来定义它们之间的关系：miniSSdj−≥iij（1）min即活动j不能在活动i开始d个单位之前处理，称ij为最小时差。0mintd0i图2：初始活动i最小差示意图min对于工程的终止活动i，最小时差事d≥Pi,n+1imin先给出，在工程最后结束前时间活动

4、d−P≥0i,n+1ii应该完成，若终止活动i仅需要在工程结束时完成，min则di,n+1=Pi。图1：活动i与j活动间的最小差示意图设i是非终止活动，若对于每个实际活动j具有min若活动j在活动i刚完成便开始，则dij=Pi，式minminmindij，而且dPij＜+则应定义jPidPin,1+=i。（1）表示一个先后约束；若活动j可以在活动i完成这样可以确保活动i在工程终止前完成。min之前开始，则活动i和活动j可以交错，有dij＜Pi。min定义3:对于活动i，j，已给d，则引入弧

5、dij=0，则活动j不能在活动i之前开始（可δdmin1dmin2dminj>的权ij:=ij，若存在ij,ij，则令收稿日期：2006—09—20作者简介：麻桂英（1969－），女,内蒙古鄂尔多斯人，副教授，研究方向：函数论。18万方数据1min2minδij＝max｛dij,dij｝。3配送运输问题的模型实例定义4:设E为AON网络的弧集，不等式例1:具有5个实际活动的实例。活动1，3在工程Sj–Si≥δij（＜i，j＞∈E）开始时便可以开始，活动5的准备时间为8个单位，该式称为时间约束。活动2最早于活动1开

6、始1个单位而最迟于它开始3个单位，活动5必须在活动4完成1个单位内执行，活动3最迟在工程开始1个单位执行，活动4在活动3执行2个单位后和最迟4个单位时间内执行，活动3在工程开始的1个时间内执行。分析：例1中给出了5项实际活动的最小最大时差。在5项实际活动以及虚拟活动0和6组成的AON网络中，初始活动1，3与虚拟活动0以弧＜0，i＞具有权δ0i=0相连结，终止活动2，4，5由弧＜j，图4：非终止活动i的最小差示意图6＞以权δ=P与虚拟活动6相连，进而，对于非终止j6j定义5:关于活动（节点）i∈V=｛0,1,…..

7、,n＋1｝min活动1，由,∀j有＜d1j+PjP1,因而应定义的一个开始时间序列，S＝｛S0，S1，S2…，Sn+1｝,minmindi,n+1:=Pi即d16=P1=6，称S为AON网络的一个调度，其中S0≥0（∀∈iV），对应弧＜1，6＞，权δ16=6。S0＝0。若S满足时间约束Sj–Si≥δij，则称S是时间则各项活动的开始时间Si的计算如下：可行的调度集合，记作ST,一个调度Sj–Si≥δij,S∈S0＝0;S1＝0;S2＝S1+δ12＝1;S4＝S3+δ34＝2;ST的工程工期Sn+1最小，则称时间最

8、优。S5＝S0+δ05＝8;定义6：设ESi和LSi为最早和最迟开始时S6＝max{S1+δ16,S2+δ26,S4+δ46,S5+δ56}间，ECi,LCi为最早和最迟的完成时间，则＝max{6,5,4,10}=10ES＝（ES0，…，ESn）称为最早调度综上,由配送的时间约束模型可得例1的配送时即：∀S∈S,ES≤S(∀i∈V),ES∈S.TiiT间约束模型：显然ES