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

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

Thedesignofthedistributionsystemisastrategicissueforalmosteverycompany.Theproblemoflocatingfacilitiesandallocatingcustomerscoversthecoretopicsofdistributionsystemdesign.

IntroductionThedesignofthedistrib3

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

Theproblemoflocatingfacilitiesisnotnewtotheoperationsresearchcommunity(運(yùn)籌學(xué));thechallengeofwheretobestsitefacilitieshasinspiredarich,colorfulandevergrowingbodyofliterature.Tocopewiththemultitudeofapplications(眾多應(yīng)用)encounteredinthebusinessworldandinthepublicsector,aneverexpandingfamilyofmodelshasemerged.TypesofmodelsTheprob5Facilitylocationmodelscanbebroadlyclassifiedasfollows:

Theshapeortopographyofthesetofpotentialplantsyieldsmodelsintheplane,networklocationmodels(網(wǎng)絡(luò)選址模型),anddiscretelocation(離散選址)ormixed-integerprogrammingmodels(混合正數(shù)規(guī)劃模型),respectively.Facilitylocationmodelscanb6Objectives(目標(biāo)函數(shù))maybeeitheroftheminsumortheminmaxtype.Minsummodelsaredesignedtominimizeaveragedistanceswhileminmaxmodelshavetominimizemaximumdistances.Predominantly(此外),minsummodelsembracelocationproblemsofprivatecompanieswhileminmaxmodelsfocusonlocationproblemsarisinginthepublicsector.Objectives(目標(biāo)函數(shù))maybeeither7Modelswithoutcapacityconstraintsdonotrestrict(限制)demandallocation.Ifcapacityconstraintsforthepotentialsiteshavetobeobeyeddemandhastobeallocatedcarefully.Inthelattercasewehavetoexaminewhethersingle-sourcing(單來(lái)源)ormultiple-sourcing(多來(lái)源)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(無(wú)彈性的),thatis,demandisindependentofspatialdecisions.Ifdemandiselastic(彈性的)therelationshipbetween,e.g.,distanceanddemandhastobetakenintoaccountexplicitly.Inthelattercasecostminimization(成本最小)hastobereplacedthrough,forexample,revenuemaximization(收益最大).物流系統(tǒng)設(shè)計(jì)的選址模型介紹(英文版)課件11Staticmodels(靜態(tài)模型)trytooptimizesystemperformance(性能)foronerepresentative(代表)period.Bycontrastdynamicmodels(動(dòng)態(tài)模型)reflectdata(cost,demand,capacities,etc.)varyingovertimewithinagivenplanninghorizon.Staticmodels(靜態(tài)模型)trytoopt12Inpracticemodel(實(shí)踐模型)inputisusuallynotknownwithcertainty.Dataarebasedonforecastsand,hence,arelikelytobeuncertain.Asaconsequence,wehaveeitherdeterministicmodels(確定模型)ifinputis(assumedtobe)knownwithcertaintyorprobabilisticmodels(概率模型)ifinputissubjecttouncertainty.Inpracticemodel(實(shí)踐模型)input13Inclassicalmodelsthequalityofdemandallocationismeasuredonisolationforeachpairofsupplyanddemandpoints.Unfortunately,ifdemandissatisfiedthroughdeliverytours(運(yùn)輸,投遞)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(隸屬關(guān)系).Theseindicatethestrengthoftheassociationbetweenthatdataelementandaparticularcluster.Fuzzyclusteringisaprocessofassigningthesemembershiplevels,andthenusingthemtoassigndataelementstooneormoreclusters.FuzzyClusteringFuzzyclusteri17gravitymethod總運(yùn)費(fèi)=設(shè)施與客戶之間的直線距離(歐幾里德距離)×需求量

對(duì)上式分別對(duì)x，y求偏微分，可以求出下面的一對(duì)隱含有最優(yōu)解的等式，應(yīng)用這兩個(gè)等式通過迭代的方法分別對(duì)x，y進(jìn)行求解，即可得最優(yōu)解。gravitymethod總運(yùn)費(fèi)=設(shè)施與客戶之間的直線距離18Cross-medianmethod總費(fèi)用=設(shè)施到需求點(diǎn)的折線距離(城市距離)×需求量上述目標(biāo)函數(shù)可以用兩個(gè)互不相干的部分來(lái)表述：其中:

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

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

GeneticalgorithmThegeneticalgorithm(G20SimulatedAnnealing

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

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

ThisproblemisNP-hard,Itcanbemodelledasthenon-linearmixed-integerprogram(非線性混合整數(shù)規(guī)劃).multi-sourceWeberproblem(MW23P-medianproblem中值問題(PMP)

P-centerproblem中值問題(PCP)其中：P-medianproblem中值問題(PMP)P-c24Uncapacitated,single-stagemodels(無(wú)容量限制單階段模型)Capacitated,single-stagemodels(有容量限制單階段模型)Uncapacitated,single-stagemo25Two-stagecapacitatedfacilitylocationproblem(帶容量限制的兩階段設(shè)施選址問題)Two-stagecapacitatedfacility26multi-productmodels(多產(chǎn)品模型)multi-productmodels(多產(chǎn)品模型)27dynamicmodels(動(dòng)態(tài)模型)dynamicmodels(動(dòng)態(tài)模型)28probabilisticmodels(概率模型)probabilisticmodels(概率模型)29Thankyou!Thankyou!30Facilitylocationmodelsfordistributionsystemdesign物流系統(tǒng)設(shè)計(jì)的選址模型Facilitylocationmodelsford31IntroductionTypesofmodelsGeneralmethodsIntroduction32

Thedesignofthedistributionsystemisastrategicissueforalmosteverycompany.Theproblemoflocatingfacilitiesandallocatingcustomerscoversthecoretopicsofdistributionsystemdesign.

IntroductionThedesignofthedistrib33

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

Theproblemoflocatingfacilitiesisnotnewtotheoperationsresearchcommunity(運(yùn)籌學(xué));thechallengeofwheretobestsitefacilitieshasinspiredarich,colorfulandevergrowingbodyofliterature.Tocopewiththemultitudeofapplications(眾多應(yīng)用)encounteredinthebusinessworldandinthepublicsector,aneverexpandingfamilyofmodelshasemerged.TypesofmodelsTheprob35Facilitylocationmodelscanbebroadlyclassifiedasfollows:

Theshapeortopographyofthesetofpotentialplantsyieldsmodelsintheplane,networklocationmodels(網(wǎng)絡(luò)選址模型),anddiscretelocation(離散選址)ormixed-integerprogrammingmodels(混合正數(shù)規(guī)劃模型),respectively.Facilitylocationmodelscanb36Objectives(目標(biāo)函數(shù))maybeeitheroftheminsumortheminmaxtype.Minsummodelsaredesignedtominimizeaveragedistanceswhileminmaxmodelshavetominimizemaximumdistances.Predominantly(此外),minsummodelsembracelocationproblemsofprivatecompanieswhileminmaxmodelsfocusonlocationproblemsarisinginthepublicsector.Objectives(目標(biāo)函數(shù))maybeeither37Modelswithoutcapacityconstraintsdonotrestrict(限制)demandallocation.Ifcapacityconstraintsforthepotentialsiteshavetobeobeyeddemandhastobeallocatedcarefully.Inthelattercasewehavetoexaminewhethersingle-sourcing(單來(lái)源)ormultiple-sourcing(多來(lái)源)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(無(wú)彈性的),thatis,demandisindependentofspatialdecisions.Ifdemandiselastic(彈性的)therelationshipbetween,e.g.,distanceanddemandhastobetakenintoaccountexplicitly.Inthelattercasecostminimization(成本最小)hastobereplacedthrough,forexample,revenuemaximization(收益最大).物流系統(tǒng)設(shè)計(jì)的選址模型介紹(英文版)課件41Staticmodels(靜態(tài)模型)trytooptimizesystemperformance(性能)foronerepresentative(代表)period.Bycontrastdynamicmodels(動(dòng)態(tài)模型)reflectdata(cost,demand,capacities,etc.)varyingovertimewithinagivenplanninghorizon.Staticmodels(靜態(tài)模型)trytoopt42Inpracticemodel(實(shí)踐模型)inputisusuallynotknownwithcertainty.Dataarebasedonforecastsand,hence,arelikelytobeuncertain.Asaconsequence,wehaveeitherdeterministicmodels(確定模型)ifinputis(assumedtobe)knownwithcertaintyorprobabilisticmodels(概率模型)ifinputissubjecttouncertainty.Inpracticemodel(實(shí)踐模型)input43Inclassicalmodelsthequalityofdemandallocationismeasuredonisolationforeachpairofsupplyanddemandpoints.Unfortunately,ifdemandissatisfiedthroughdeliverytours(運(yùn)輸,投遞)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(隸屬關(guān)系).Theseindicatethestrengthoftheassociationbetweenthatdataelementandaparticularcluster.Fuzzyclusteringisaprocessofassigningthesemembershiplevels,andthenusingthemtoassigndataelementstooneormoreclusters.FuzzyClusteringFuzzyclusteri47gravitymethod總運(yùn)費(fèi)=設(shè)施與客戶之間的直線距離(歐幾里德距離)×需求量

對(duì)上式分別對(duì)x，y求偏微分，可以求出下面的一對(duì)隱含有最優(yōu)解的等式，應(yīng)用這兩個(gè)等式通過迭代的方法分別對(duì)x，y進(jìn)行求解，即可得最優(yōu)解。gravitymethod總運(yùn)費(fèi)=設(shè)施與客戶之間的直線距離48Cross-medianmethod總費(fèi)用=設(shè)施到需求點(diǎn)的折線距離(城市距離)×需求量上述目標(biāo)函數(shù)可以用兩個(gè)互不相干的部分來(lái)表述：其中:

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

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