带时间窗车辆路径问题及其启发式算法研究

《带时间窗车辆路径问题及其启发式算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、合肥工业大学博士学位论文带时间窗车辆路径问题及其启发式算法研究姓名：马华伟申请学位级别：博士专业：计算机及应用指导教师：杨善林20081101(4)引入模拟退火算法求解带时间窗问题的扩展问题。本文改进基本的模拟退火算法用于求解带时间窗问题及其扩展问题，并简化邻域构造技术以提高算法效率，实验表明改进的模拟退火算法能够有效地求解带时间窗问题及其扩展问题。关键词：车辆路径问题时间窗车辆流模型模拟退火算法ABSTRACTVehicleRoutingProblemisaclassofoptimizationproblems，ofwhichtheobjectiveistocon

2、structasetoffeasibleroutestoreducetransportationcosts．Thecorrelativetheoriesandmethodshavegreatapplicationvaluesforreducingthelogisticcost，SOtheyarealwaysthehotspotofoperationsresearchandcombinatorialoptimizationdomains．Inrecentyears，thevehicleroutingproblemhasgeneratedalotofbranches，s

3、uchasopenvehicleroutingproblem，multi—depotvehicleroutingproblem，pickupanddelieveryproblem，vehicleroutingproblemwithtimewindow,periodicvehicleroutingproblemandSOon,andmanyimprovementshavebeenachieved．Whilethevehicleroutingproblemhasbeenwidelyappliedtomanyaspectsinreallifeandproduction,s

4、uchasmaildelievery,goodsdelieveryandvehiclesschedulingandSOon，greatbenefithasbeengained．Inreallifethereisaclassofvehicleroutingproblems：thecustomershavestrictlimittotheirservicetime，andtheyhopetheyCanbeservedinappointedtimeintervals，SOthecapacityconstraintandthetimeconstraintwillbecons

5、ideredsimultaneouslywhileconstructingtheroutes．ThisclassofproblemsiscalledVehicleRoutingProblemwithTimeWindow,inwhichthetimeintervalsarecalledtimewindow．Sincethetimewindowisintroduced，thevehicleroutingproblemwithtimewindowishardertosolve，SOitisalwaysoneofthemostimportantbranchesinvehic

6、leroutingproblems．Themodelsandmethodsaboutvehicleroutingproblemwithtimewindowanditsextendedproblemsarestudiedinthispaper,themaincontributionsofthispaperaresummarizedaSfollows：(1)Arulecalled“First-expired-fh-st-served”isproposedtosolvethevehicleroutingproblemwithtimewindowanditsextended

7、problems．ThevehicleroutingproblemwithtimewindowanditsextendedproblemshavebeenprovedtobeNP-Hard，andheuristicmethodsareusuallyusedtogainsatisfyingsolution．ThispaperstudiesthebaSicvehicleroutingproblemwithsingletimewindowundertimeindependent，analyzingmanycommonalgorithmsandproposedarule