物流系统设计的选址模型介绍(英文版)课件

Facilitylocationmodelsfordistributionsystemdesign物流系统设计的选址模型Facilitylocationmodelsford1IntroductionTypesofmodelsGeneralmethodsIntroduction2

Thedesignofthedistributionsystemisastrategicissueforalmosteverycompany.Theproblemoflocatingfacilitiesandallocatingcustomerscoversthecoretopicsofdistributionsystemdesign.

IntroductionThedesignofthedistrib3

Industrialfirmsmustlocatefabrication(制造厂)andassemblyplants(组装厂)aswellaswarehouses(仓库).Storeshavetobelocatedbyretailoutlets(零售网点).Theabilitytomanufactureandmarketitsproductsisdependentinpartonthelocationofthefacilities.Similarly,governmentagencieshavetodecideaboutthelocationofoffices,schools,hospitals,firestations,etc.Ineverycase,thequalityoftheservicesdependsonthelocationofthefacilitiesinrelationtootherfacilities.Industrialfirmsmustloc4Typesofmodels

Theproblemoflocatingfacilitiesisnotnewtotheoperationsresearchcommunity(运筹学);thechallengeofwheretobestsitefacilitieshasinspiredarich,colorfulandevergrowingbodyofliterature.Tocopewiththemultitudeofapplications(众多应用)encounteredinthebusinessworldandinthepublicsector,aneverexpandingfamilyofmodelshasemerged.TypesofmodelsTheprob5Facilitylocationmodelscanbebroadlyclassifiedasfollows:

Theshapeortopographyofthesetofpotentialplantsyieldsmodelsintheplane,networklocationmodels(网络选址模型),anddiscretelocation(离散选址)ormixed-integerprogrammingmodels(混合正数规划模型),respectively.Facilitylocationmodelscanb6Objectives(目标函数)maybeeitheroftheminsumortheminmaxtype.Minsummodelsaredesignedtominimizeaveragedistanceswhileminmaxmodelshavetominimizemaximumdistances.Predominantly(此外),minsummodelsembracelocationproblemsofprivatecompanieswhileminmaxmodelsfocusonlocationproblemsarisinginthepublicsector.Objectives(目标函数)maybeeither7Modelswithoutcapacityconstraintsdonotrestrict(限制)demandallocation.Ifcapacityconstraintsforthepotentialsiteshavetobeobeyeddemandhastobeallocatedcarefully.Inthelattercasewehavetoexaminewhethersingle-sourcing(单来源)ormultiple-sourcing(多来源)isessential.Modelswithoutcapacityconstr8Single-stagemodels(单阶段模型)focusondistributionsystemscoveringonlyonestageexplicitly.Inmulti-stagemodels(多阶段模型)theflowofgoodscomprisingseveralhierarchical(层次)stageshastobeexamined.Single-stagemodels(单阶段模型)foc9Single-productmodels(单产品模型)arecharacterizedbythefactthatdemand,costandcapacityforseveralproductscanbeaggregatedtoasinglehomogeneousproduct.Ifproductsareinhomogeneoustheireffectonthedesignofthedistributionsystemhastobeanalyzed,viz.multi-productmodels(多产品模型)havetobestudied.Single-productmodels(单产品模型)a10Locationmodelsbaseontheassumptionthatdemandisinelastic(无弹性的),thatis,demandisindependentofspatialdecisions.Ifdemandiselastic(弹性的)therelationshipbetween,e.g.,distanceanddemandhastobetakenintoaccountexplicitly.Inthelattercasecostminimization(成本最小)hastobereplacedthrough,forexample,revenuemaximization(收益最大).物流系统设计的选址模型介绍(英文版)课件11Staticmodels(静态模型)trytooptimizesystemperformance(性能)foronerepresentative(代表)period.Bycontrastdynamicmodels(动态模型)reflectdata(cost,demand,capacities,etc.)varyingovertimewithinagivenplanninghorizon.Staticmodels(静态模型)trytoopt12Inpracticemodel(实践模型)inputisusuallynotknownwithcertainty.Dataarebasedonforecastsand,hence,arelikelytobeuncertain.Asaconsequence,wehaveeitherdeterministicmodels(确定模型)ifinputis(assumedtobe)knownwithcertaintyorprobabilisticmodels(概率模型)ifinputissubjecttouncertainty.Inpracticemodel(实践模型)input13Inclassicalmodelsthequalityofdemandallocationismeasuredonisolationforeachpairofsupplyanddemandpoints.Unfortunately,ifdemandissatisfiedthroughdeliverytours(运输,投递)then,forinstance,deliverycostcannotbecalculatedforeachpairofsupplyanddemandpointsseparately.Combinedlocation/routingmodels(选址/路线模型)elaborateonthisinterrelationship.Inclassicalmodelsthequalit14GeneralmethodsAHP(AnalyticHierarchyProcess)层次分析法FuzzyClustering模糊聚类法Cross-medianmethod交叉中值法gravitymethod重心法P-medianmethodP-中值法Systemicarithmetic系统模拟法Geneticalgorithm(GA)遗传算法Theshortestpathmethod最短路径法SimulatedAnnealing(SA)模拟退火算法GeneralmethodsAHP(AnalyticH15TheAnalyticHierarchyProcess(AHP)isastructuredtechniquefordealingwithcomplexdeciision.Ratherthanprescribinga"correct"decision,theAHPhelpsthedecisionmakersfindonethatbestsuitstheirgoalandtheirunderstandingoftheproblem.Basedonmathematicsandpsychology,theAHPwasdevelopedbyThomasL.Saatyinthe1970sandhasbeenextensivelystudiedandrefinedsincethen.Itprovidesacomprehensive(全面)andrationalframework（合理的框架）forstructuringadecisionproblem（结构化决策问题）,forrepresentingandquantifyingitselements,forrelatingthoseelementstooverallgoals,andforevaluatingalternativesolutions.Itisusedaroundtheworldinawidevarietyofdecisionsituations,infieldssuchasgovernment,business,industry,healthcare,andeducation.AHPTheAnalyticHierarchyProcess16FuzzyClusteringFuzzyclusteringisaclassofalgorithmsforclusteranalysisinwhichtheallocationofdatapointstoclustersisnot"hard"(all-or-nothing)but"fuzzy"inthesamesenseasfuzzylogic.Inhardclustering,dataisdividedintodistinctclusters,whereeachdataelementbelongstoexactlyonecluster.Infuzzyclustering(alsoreferredtoassoftclustering),dataelementscanbelongtomorethanonecluster,andassociatedwitheachelementisasetofmembershiplevels(隶属关系).Theseindicatethestrengthoftheassociationbetweenthatdataelementandaparticularcluster.Fuzzyclusteringisaprocessofassigningthesemembershiplevels,andthenusingthemtoassigndataelementstooneormoreclusters.FuzzyClusteringFuzzyclusteri17gravitymethod总运费=设施与客户之间的直线距离(欧几里德距离)×需求量

对上式分别对x，y求偏微分，可以求出下面的一对隐含有最优解的等式，应用这两个等式通过迭代的方法分别对x，y进行求解，即可得最优解。gravitymethod总运费=设施与客户之间的直线距离18Cross-medianmethod总费用=设施到需求点的折线距离(城市距离)×需求量上述目标函数可以用两个互不相干的部分来表述：其中:

最优位置是由如下坐标组成的点:xs是在x方向的所有的权重wi的中值点,ys是在y方向的所有的权重wi的中值点。Cross-medianmethod总费用=设施到需求点的19

Thegeneticalgorithm(GA)isasearchheuristic(启发式)thatmimics(模仿)theprocessofnaturalevolution.Thisheuristicisroutinelyusedtogenerateusefulsolutionstooptimizationandsearchproblems.Geneticalgorithmsbelongtothelargerclassofevolutionaryalgorithms(EA)(进化算法),whichgeneratesolutions(生成解决方案)tooptimizationproblemsusingtechniquesinspiredbynaturalevolution,suchasinheritance(继承),mutation(突变),selection(选择),andcrossover(杂交).

GeneticalgorithmThegeneticalgorithm(G20SimulatedAnnealing

Simulatedannealing(SA)isagenericprobabilisticmetaheuristic(启发式)fortheglobaloptimizationproblemofappliedmathematics(应用数学),namelylocatingagoodapproximation(逼近)totheglobaloptimumofagivenfunctioninalargesearchspace.Itisoftenusedwhenthesearchspaceisdiscrete(e.g.,alltoursthatvisitagivensetofcities).Forcertainproblems,simulatedannealingmaybemoreeffectivethanexhaustiveenumeration(穷举法)—providedthatthegoalismerelytofindanacceptablygoodsolutioninafixedamountoftime,ratherthanthebestpossiblesolution.SimulatedAnnealingSimu21MinisumMinimaxMaximin

Minisum被称为网络上的中值问题。Minimax被称为网络上的中心问题。Maximin被称为反中心问题(Anti-Center)。假设在一条直线上，在位置0,5,6和7上有4个点。为每个点服务的成本与这些点和新设施间的距离成正比。对于Minisum目标来说，新设施的最优位置是这些点的中值5.5，即在选址的左边和右边有相同多的点。对于Minimax目标来说，最优位置就是这些点的中心3.5，即选址位置到最左边点和最右边点的距离是相等的。对于Maximin目标来说最优位置是反中心点2.5。Maximin目标由已存在设施中成本最小的个体组成，目标是使最坏的情况最优化。MinisumMinimaxMaximin22multi-sourceWeberproblem(MWP)多来源韦伯问题

ThisproblemisNP-hard,Itcanbemodelledasthenon-linearmixed-integerprogram(非线性混合整数规划).multi-sourceWeberproblem(MW23P-medianproblem中值问题(PMP)

P-centerproblem中值问题(PCP)其中：P-medianproblem中值问题(PMP)P-c24Uncapacitated,single-stagemodels(无容量限制单阶段模型)Capacitated,single-stagemodels(有容量限制单阶段模型)Uncapacitated,single-stagemo25Two-stagecapacitatedfacilitylocationproblem(带容量限制的两阶段设施选址问题)Two-stagecapacitatedfacility26multi-productmodels(多产品模型)multi-productmodels(多产品模型)27dynamicmodels(动态模型)dynamicmodels(动态模型)28probabilisticmodels(概率模型)probabilisticmodels(概率模型)29Thankyou!Thankyou!30Facilitylocationmodelsfordistributionsystemdesign物流系统设计的选址模型Facilitylocationmodelsford31IntroductionTypesofmodelsGeneralmethodsIntroduction32

Thedesignofthedistributionsystemisastrategicissueforalmosteverycompany.Theproblemoflocatingfacilitiesandallocatingcustomerscoversthecoretopicsofdistributionsystemdesign.

IntroductionThedesignofthedistrib33

Industrialfirmsmustlocatefabrication(制造厂)andassemblyplants(组装厂)aswellaswarehouses(仓库).Storeshavetobelocatedbyretailoutlets(零售网点).Theabilitytomanufactureandmarketitsproductsisdependentinpartonthelocationofthefacilities.Similarly,governmentagencieshavetodecideaboutthelocationofoffices,schools,hospitals,firestations,etc.Ineverycase,thequalityoftheservicesdependsonthelocationofthefacilitiesinrelationtootherfacilities.Industrialfirmsmustloc34Typesofmodels

Theproblemoflocatingfacilitiesisnotnewtotheoperationsresearchcommunity(运筹学);thechallengeofwheretobestsitefacilitieshasinspiredarich,colorfulandevergrowingbodyofliterature.Tocopewiththemultitudeofapplications(众多应用)encounteredinthebusinessworldandinthepublicsector,aneverexpandingfamilyofmodelshasemerged.TypesofmodelsTheprob35Facilitylocationmodelscanbebroadlyclassifiedasfollows:

Theshapeortopographyofthesetofpotentialplantsyieldsmodelsintheplane,networklocationmodels(网络选址模型),anddiscretelocation(离散选址)ormixed-integerprogrammingmodels(混合正数规划模型),respectively.Facilitylocationmodelscanb36Objectives(目标函数)maybeeitheroftheminsumortheminmaxtype.Minsummodelsaredesignedtominimizeaveragedistanceswhileminmaxmodelshavetominimizemaximumdistances.Predominantly(此外),minsummodelsembracelocationproblemsofprivatecompanieswhileminmaxmodelsfocusonlocationproblemsarisinginthepublicsector.Objectives(目标函数)maybeeither37Modelswithoutcapacityconstraintsdonotrestrict(限制)demandallocation.Ifcapacityconstraintsforthepotentialsiteshavetobeobeyeddemandhastobeallocatedcarefully.Inthelattercasewehavetoexaminewhethersingle-sourcing(单来源)ormultiple-sourcing(多来源)isessential.Modelswithoutcapacityconstr38Single-stagemodels(单阶段模型)focusondistributionsystemscoveringonlyonestageexplicitly.Inmulti-stagemodels(多阶段模型)theflowofgoodscomprisingseveralhierarchical(层次)stageshastobeexamined.Single-stagemodels(单阶段模型)foc39Single-productmodels(单产品模型)arecharacterizedbythefactthatdemand,costandcapacityforseveralproductscanbeaggregatedtoasinglehomogeneousproduct.Ifproductsareinhomogeneoustheireffectonthedesignofthedistributionsystemhastobeanalyzed,viz.multi-productmodels(多产品模型)havetobestudied.Single-productmodels(单产品模型)a40Locationmodelsbaseontheassumptionthatdemandisinelastic(无弹性的),thatis,demandisindependentofspatialdecisions.Ifdemandiselastic(弹性的)therelationshipbetween,e.g.,distanceanddemandhastobetakenintoaccountexplicitly.Inthelattercasecostminimization(成本最小)hastobereplacedthrough,forexample,revenuemaximization(收益最大).物流系统设计的选址模型介绍(英文版)课件41Staticmodels(静态模型)trytooptimizesystemperformance(性能)foronerepresentative(代表)period.Bycontrastdynamicmodels(动态模型)reflectdata(cost,demand,capacities,etc.)varyingovertimewithinagivenplanninghorizon.Staticmodels(静态模型)trytoopt42Inpracticemodel(实践模型)inputisusuallynotknownwithcertainty.Dataarebasedonforecastsand,hence,arelikelytobeuncertain.Asaconsequence,wehaveeitherdeterministicmodels(确定模型)ifinputis(assumedtobe)knownwithcertaintyorprobabilisticmodels(概率模型)ifinputissubjecttouncertainty.Inpracticemodel(实践模型)input43Inclassicalmodelsthequalityofdemandallocationismeasuredonisolationforeachpairofsupplyanddemandpoints.Unfortunately,ifdemandissatisfiedthroughdeliverytours(运输,投递)then,forinstance,deliverycostcannotbecalculatedforeachpairofsupplyanddemandpointsseparately.Combinedlocation/routingmodels(选址/路线模型)elaborateonthisinterrelationship.Inclassicalmodelsthequalit44GeneralmethodsAHP(AnalyticHierarchyProcess)层次分析法FuzzyClustering模糊聚类法Cross-medianmethod交叉中值法gravitymethod重心法P-medianmethodP-中值法Systemicarithmetic系统模拟法Geneticalgorithm(GA)遗传算法Theshortestpathmethod最短路径法SimulatedAnnealing(SA)模拟退火算法GeneralmethodsAHP(AnalyticH45TheAnalyticHierarchyProcess(AHP)isastructuredtechniquefordealingwithcomplexdeciision.Ratherthanprescribinga"correct"decision,theAHPhelpsthedecisionmakersfindonethatbestsuitstheirgoalandtheirunderstandingoftheproblem.Basedonmathematicsandpsychology,theAHPwasdevelopedbyThomasL.Saatyinthe1970sandhasbeenextensivelystudiedandrefinedsincethen.Itprovidesacomprehensive(全面)andrationalframework（合理的框架）forstructuringadecisionproblem（结构化决策问题）,forrepresentingandquantifyingitselements,forrelatingthoseelementstooverallgoals,andforevaluatingalternativesolutions.Itisusedaroundtheworldinawidevarietyofdecisionsituations,infieldssuchasgovernment,business,industry,healthcare,andeducation.AHPTheAnalyticHierarchyProcess46FuzzyClusteringFuzzyclusteringisaclassofalgorithmsforclusteranalysisinwhichtheallocationofdatapointstoclustersisnot"hard"(all-or-nothing)but"fuzzy"inthesamesenseasfuzzylogic.Inhardclustering,dataisdividedintodistinctclusters,whereeachdataelementbelongstoexactlyonecluster.Infuzzyclustering(alsoreferredtoassoftclustering),dataelementscanbelongtomorethanonecluster,andassociatedwitheachelementisasetofmembershiplevels(隶属关系).Theseindicatethestrengthoftheassociationbetweenthatdataelementandaparticularcluster.Fuzzyclusteringisaprocessofassigningthesemembershiplevels,andthenusingthemtoassigndataelementstooneormoreclusters.FuzzyClusteringFuzzyclusteri47gravitymethod总运费=设施与客户之间的直线距离(欧几里德距离)×需求量

对上式分别对x，y求偏微分，可以求出下面的一对隐含有最优解的等式，应用这两个等式通过迭代的方法分别对x，y进行求解，即可得最优解。gravitymethod总运费=设施与客户之间的直线距离48Cross-medianmethod总费用=设施到需求点的折线距离(城市距离)×需求量上述目标函数可以用两个互不相干的部分来表述：其中:

最优位置是由如下坐标组成的点:xs是在x方向的所有的权重wi的中值点,ys是在y方向的所有的权重wi的中值点。Cross-medianmethod总费用=设施到需求点的49

Thegeneticalgorithm(GA)isasearchheuristic(启发式)thatmimics(模仿)theprocessofnaturalevolution.Thisheuristicisroutinelyusedtogenerateusefulsolutionstooptimizationandsearchproblems.Geneticalgorithmsbelongtothelargerclassofevolutionaryalgorithms(EA)(进化算法),whichgeneratesolutions(生成解决方案)tooptimizationproblemsusingtechniquesinspiredbynaturalevolution,suchasinheritance(继承),mutation(突变),selection(选择),andcrossover(杂交).