物流系統(tǒng)設計的選址模型介紹(英文版)課件

Facilitylocationmodelsfordistributionsystemdesign物流系統(tǒng)設計的選址模型Facilitylocationmodelsford1IntroductionTypesofmodelsGeneralmethodsIntroduction2

Thedesignofthedistributionsystemisastrategicissueforalmosteverycompany.Theproblemoflocatingfacilitiesandallocatingcustomerscoversthecoretopicsofdistributionsystemdesign.

IntroductionThedesignofthedistrib3

Industrialfirmsmustlocatefabrication(制造廠)andassemblyplants(組裝廠)aswellaswarehouses(倉庫).Storeshavetobelocatedbyretailoutlets(零售網(wǎng)點).Theabilitytomanufactureandmarketitsproductsisdependentinpartonthelocationofthefacilities.Similarly,governmentagencieshavetodecideaboutthelocationofoffices,schools,hospitals,firestations,etc.Ineverycase,thequalityoftheservicesdependsonthelocationofthefacilitiesinrelationtootherfacilities.Industrialfirmsmustloc4Typesofmodels

Theproblemoflocatingfacilitiesisnotnewtotheoperationsresearchcommunity(運籌學);thechallengeofwheretobestsitefacilitieshasinspiredarich,colorfulandevergrowingbodyofliterature.Tocopewiththemultitudeofapplications(眾多應用)encounteredinthebusinessworldandinthepublicsector,aneverexpandingfamilyofmodelshasemerged.TypesofmodelsTheprob5Facilitylocationmodelscanbebroadlyclassifiedasfollows:

Theshapeortopographyofthesetofpotentialplantsyieldsmodelsintheplane,networklocationmodels(網(wǎng)絡選址模型),anddiscretelocation(離散選址)ormixed-integerprogrammingmodels(混合正數(shù)規(guī)劃模型),respectively.Facilitylocationmodelscanb6Objectives(目標函數(shù))maybeeitheroftheminsumortheminmaxtype.Minsummodelsaredesignedtominimizeaveragedistanceswhileminmaxmodelshavetominimizemaximumdistances.Predominantly(此外),minsummodelsembracelocationproblemsofprivatecompanieswhileminmaxmodelsfocusonlocationproblemsarisinginthepublicsector.Objectives(目標函數(shù))maybeeither7Modelswithoutcapacityconstraintsdonotrestrict(限制)demandallocation.Ifcapacityconstraintsforthepotentialsiteshavetobeobeyeddemandhastobeallocatedcarefully.Inthelattercasewehavetoexaminewhethersingle-sourcing(單來源)ormultiple-sourcing(多來源)isessential.Modelswithoutcapacityconstr8Single-stagemodels(單階段模型)focusondistributionsystemscoveringonlyonestageexplicitly.Inmulti-stagemodels(多階段模型)theflowofgoodscomprisingseveralhierarchical(層次)stageshastobeexamined.Single-stagemodels(單階段模型)foc9Single-productmodels(單產(chǎn)品模型)arecharacterizedbythefactthatdemand,costandcapacityforseveralproductscanbeaggregatedtoasinglehomogeneousproduct.Ifproductsareinhomogeneoustheireffectonthedesignofthedistributionsystemhastobeanalyzed,viz.multi-productmodels(多產(chǎn)品模型)havetobestudied.Single-productmodels(單產(chǎn)品模型)a10Locationmodelsbaseontheassumptionthatdemandisinelastic(無彈性的),thatis,demandisindependentofspatialdecisions.Ifdemandiselastic(彈性的)therelationshipbetween,e.g.,distanceanddemandhastobetakenintoaccountexplicitly.Inthelattercasecostminimization(成本最小)hastobereplacedthrough,forexample,revenuemaximization(收益最大).物流系統(tǒng)設計的選址模型介紹(英文版)課件11Staticmodels(靜態(tài)模型)trytooptimizesystemperformance(性能)foronerepresentative(代表)period.Bycontrastdynamicmodels(動態(tài)模型)reflectdata(cost,demand,capacities,etc.)varyingovertimewithinagivenplanninghorizon.Staticmodels(靜態(tài)模型)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系統(tǒng)模擬法Geneticalgorithm(GA)遺傳算法Theshortestpathmethod最短路徑法SimulatedAnnealing(SA)模擬退火算法GeneralmethodsAHP(AnalyticH15TheAnalyticHierarchyProcess(AHP)isastructuredtechniquefordealingwithcomplexdeciision.Ratherthanprescribinga"correct"decision,theAHPhelpsthedecisionmakersfindonethatbestsuitstheirgoalandtheirunderstandingoftheproblem.Basedonmathematicsandpsychology,theAHPwasdevelopedbyThomasL.Saatyinthe1970sandhasbeenextensivelystudiedandrefinedsincethen.Itprovidesacomprehensive(全面)andrationalframework（合理的框架）forstructuringadecisionproblem（結(jié)構(gòu)化決策問題）,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求偏微分，可以求出下面的一對隱含有最優(yōu)解的等式，應用這兩個等式通過迭代的方法分別對x，y進行求解，即可得最優(yōu)解。gravitymethod總運費=設施與客戶之間的直線距離18Cross-medianmethod總費用=設施到需求點的折線距離(城市距離)×需求量上述目標函數(shù)可以用兩個互不相干的部分來表述：其中:

最優(yōu)位置是由如下坐標組成的點:xs是在x方向的所有的權重wi的中值點,ys是在y方向的所有的權重wi的中值點。Cross-medianmethod總費用=設施到需求點的19

Thegeneticalgorithm(GA)isasearchheuristic(啟發(fā)式)thatmimics(模仿)theprocessofnaturalevolution.Thisheuristicisroutinelyusedtogenerateusefulsolutionstooptimizationandsearchproblems.Geneticalgorithmsbelongtothelargerclassofevolutionaryalgorithms(EA)(進化算法),whichgeneratesolutions(生成解決方案)tooptimizationproblemsusingtechniquesinspiredbynaturalevolution,suchasinheritance(繼承),mutation(突變),selection(選擇),andcrossover(雜交).

GeneticalgorithmThegeneticalgorithm(G20SimulatedAnnealing

Simulatedannealing(SA)isagenericprobabilisticmetaheuristic(啟發(fā)式)fortheglobaloptimizationproblemofappliedmathematics(應用數(shù)學),namelylocatingagoodapproximation(逼近)totheglobaloptimumofagivenfunctioninalargesearchspace.Itisoftenusedwhenthesearchspaceisdiscrete(e.g.,alltoursthatvisitagivensetofcities).Forcertainproblems,simulatedannealingmaybemoreeffectivethanexhaustiveenumeration(窮舉法)—providedthatthegoalismerelytofindanacceptablygoodsolutioninafixedamountoftime,ratherthanthebestpossiblesolution.SimulatedAnnealingSimu21MinisumMinimaxMaximin

Minisum被稱為網(wǎng)絡上的中值問題。Minimax被稱為網(wǎng)絡上的中心問題。Maximin被稱為反中心問題(Anti-Center)。假設在一條直線上，在位置0,5,6和7上有4個點。為每個點服務的成本與這些點和新設施間的距離成正比。對于Minisum目標來說，新設施的最優(yōu)位置是這些點的中值5.5，即在選址的左邊和右邊有相同多的點。對于Minimax目標來說，最優(yōu)位置就是這些點的中心3.5，即選址位置到最左邊點和最右邊點的距離是相等的。對于Maximin目標來說最優(yōu)位置是反中心點2.5。Maximin目標由已存在設施中成本最小的個體組成，目標是使最壞的情況最優(yōu)化。MinisumMinimaxMaximin22multi-sourceWeberproblem(MWP)多來源韋伯問題

ThisproblemisNP-hard,Itcanbemodelledasthenon-linearmixed-integerprogram(非線性混合整數(shù)規(guī)劃).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(多產(chǎn)品模型)multi-productmodels(多產(chǎn)品模型)27dynamicmodels(動態(tài)模型)dynamicmodels(動態(tài)模型)28probabilisticmodels(概率模型)probabilisticmodels(概率模型)29Thankyou!Thankyou!30Facilitylocationmodelsfordistributionsystemdesign物流系統(tǒng)設計的選址模型Facilitylocationmodelsford31IntroductionTypesofmodelsGeneralmethodsIntroduction32

Thedesignofthedistributionsystemisastrategicissueforalmosteverycompany.Theproblemoflocatingfacilitiesandallocatingcustomerscoversthecoretopicsofdistributionsystemdesign.

IntroductionThedesignofthedistrib33

Industrialfirmsmustlocatefabrication(制造廠)andassemblyplants(組裝廠)aswellaswarehouses(倉庫).Storeshavetobelocatedbyretailoutlets(零售網(wǎng)點).Theabilitytomanufactureandmarketitsproductsisdependentinpartonthelocationofthefacilities.Similarly,governmentagencieshavetodecideaboutthelocationofoffices,schools,hospitals,firestations,etc.Ineverycase,thequalityoftheservicesdependsonthelocationofthefacilitiesinrelationtootherfacilities.Industrialfirmsmustloc34Typesofmodels

Theproblemoflocatingfacilitiesisnotnewtotheoperationsresearchcommunity(運籌學);thechallengeofwheretobestsitefacilitieshasinspiredarich,colorfulandevergrowingbodyofliterature.Tocopewiththemultitudeofapplications(眾多應用)encounteredinthebusinessworldandinthepublicsector,aneverexpandingfamilyofmodelshasemerged.TypesofmodelsTheprob35Facilitylocationmodelscanbebroadlyclassifiedasfollows:

Theshapeortopographyofthesetofpotentialplantsyieldsmodelsintheplane,networklocationmodels(網(wǎng)絡選址模型),anddiscretelocation(離散選址)ormixed-integerprogrammingmodels(混合正數(shù)規(guī)劃模型),respectively.Facilitylocationmodelscanb36Objectives(目標函數(shù))maybeeitheroftheminsumortheminmaxtype.Minsummodelsaredesignedtominimizeaveragedistanceswhileminmaxmodelshavetominimizemaximumdistances.Predominantly(此外),minsummodelsembracelocationproblemsofprivatecompanieswhileminmaxmodelsfocusonlocationproblemsarisinginthepublicsector.Objectives(目標函數(shù))maybeeither37Modelswithoutcapacityconstraintsdonotrestrict(限制)demandallocation.Ifcapacityconstraintsforthepotentialsiteshavetobeobeyeddemandhastobeallocatedcarefully.Inthelattercasewehavetoexaminewhethersingle-sourcing(單來源)ormultiple-sourcing(多來源)isessential.Modelswithoutcapacityconstr38Single-stagemodels(單階段模型)focusondistributionsystemscoveringonlyonestageexplicitly.Inmulti-stagemodels(多階段模型)theflowofgoodscomprisingseveralhierarchical(層次)stageshastobeexamined.Single-stagemodels(單階段模型)foc39Single-productmodels(單產(chǎn)品模型)arecharacterizedbythefactthatdemand,costandcapacityforseveralproductscanbeaggregatedtoasinglehomogeneousproduct.Ifproductsareinhomogeneoustheireffectonthedesignofthedistributionsystemhastobeanalyzed,viz.multi-productmodels(多產(chǎn)品模型)havetobestudied.Single-productmodels(單產(chǎn)品模型)a40Locationmodelsbaseontheassumptionthatdemandisinelastic(無彈性的),thatis,demandisindependentofspatialdecisions.Ifdemandiselastic(彈性的)therelationshipbetween,e.g.,distanceanddemandhastobetakenintoaccountexplicitly.Inthelattercasecostminimization(成本最小)hastobereplacedthrough,forexample,revenuemaximization(收益最大).物流系統(tǒng)設計的選址模型介紹(英文版)課件41Staticmodels(靜態(tài)模型)trytooptimizesystemperformance(性能)foronerepresentative(代表)period.Bycontrastdynamicmodels(動態(tài)模型)reflectdata(cost,demand,capacities,etc.)varyingovertimewithinagivenplanninghorizon.Staticmodels(靜態(tài)模型)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系統(tǒng)模擬法Geneticalgorithm(GA)遺傳算法Theshortestpathmethod最短路徑法SimulatedAnnealing(SA)模擬退火算法GeneralmethodsAHP(AnalyticH45TheAnalyticHierarchyProcess(AHP)isastructuredtechniquefordealingwithcomplexdeciision.Ratherthanprescribinga"correct"decision,theAHPhelpsthedecisionmakersfindonethatbestsuitstheirgoalandtheirunderstandingoftheproblem.Basedonmathematicsandpsychology,theAHPwasdevelopedbyThomasL.Saatyinthe1970sandhasbeenextensivelystudiedandrefinedsincethen.Itprovidesacomprehensive(全面)andrationalframework（合理的框架）forstructuringadecisionproblem（結(jié)構(gòu)化決策問題）,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求偏微分，可以求出下面的一對隱含有最優(yōu)解的等式，應用這兩個等式通過迭代的方法分別對x，y進行求解，即可得最優(yōu)解。gravitymethod總運費=設施與客戶之間的直線距離48Cross-medianmethod總費用=設施到需求點的折線距離(城市距離)×需求量上述目標函數(shù)可以用兩個互不相干的部分來表述：其中:

最優(yōu)位置是由如下坐標組成的點:xs是在x方向的所有的權重wi的中值點,ys是在y方向的所有的權重wi的中值點。Cross-medianmethod總費用=設施到需求點的49

Thegeneticalgorithm(GA)isasearchheuristic(啟發(fā)式)thatmimics(模仿)theprocessofnaturalevolution.Thisheuristicisroutinelyusedtogenerateusefulsolutionstooptimizationandsearchproblems.Geneticalgorithmsbelongtothelargerclassofevolutionaryalgorithms(EA)(進化算法),whichgeneratesolutions(生成解決方案)tooptimizationproblemsusingtechniquesinspiredbynaturalevolution,suchasinheritance(繼承),mutation(突變),selection(選擇),andcrossover(雜交).