一类复杂PDPTW问题的启发式算法研究

《一类复杂PDPTW问题的启发式算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一类复杂PDPTW的启发式算法研究摘要有时间窗口的装卸货问题(PDPTW)是个运筹学问题，在工农业生产、经济领域、交通、物流管理、资源调配等方面有着广泛的现实意义，IN时它又是组合优化问题中一个典型的NP-hard问题，因此戮‘今鬯j筹学与组合优化领域的研究的难点与热点问题。?悯题的复杂性，目前对PDPTW的研究还相对很少，特别是：{}0茹I王还没有相关文献。因此对此问题的解决还需要艰苦的工作。习题都存在一定的规模，精确解不易求得，所以目前对此类f究重点在于启发式算法上。尤是关于复杂PDPTW的启发式算法的研究，旨在寻找能够鱼解决实际PDPTW问题的方法。这里的复杂PDPTW

2、是指：挺。多车库、多货物类型以及有最大工作时间限制的PDPTW，一心的应用环境更多，但模型更复杂，研究难度更大。j州r。‘本女将一些新的启发式思想引入到复杂PDPTW中，取得了一定的成效，主要研究成果如下：1．提出了自己的插入启发式算法，一种是基于solomn的改进插厂入启发式算法，另一种是结合聚类思想的插入启发式算法。饼且给出L了如何将插入启发式算法进行扩展以处理复杂PDPTW的方法。这两种插入启发式算法都具有兼容性和扩展性，都能处理一般PDPTw和，／√复杂PDPTW，且计算迅速，并能保证解的质量的优良性和稳定性。／Y，2．提出了降低插入算法复杂度的方法，并给出了方法的证

3、明。厂通过对改进前后的算法复杂凄分析，涯甥了改进后的冀法复杂度比改l进前的降低了一个D俐等级(其中”是问题中客户总数)。，，V”一3．在前面研究韵瑾论基础鞫积累黪经验上，以快速减少车辆数圈为目标，提出了～种独特的启发式算法。f这是一种基于局域搜索和t随祝扰动思想的启发式算法。先强制将短路径的客户捶入到长路径，使得快速搜索到局部最小点，再用随机扰动跳到另一个区域重新开始援索。此算法的最大静祷点就是：抉且有效，可以迅速减少车辆数爨。／f’4．将插入启发式算法和快速算法结合起来共同解决复杂PDPTW，更加提高了解的质鐾的优良性帮稳定性。艇解决复杂、PDPTW的过程分为两个阶段，第一

4、步先用插入启发式算法构造一个质量较好的初始解，第二步馏快速算法对初始解进行改避，迅速且有效地提高解的质量。，譬一一。上面的算法都用C语言实现，并用PDPTW实倒进行了性能测试。，最终的实验结果分析表明上述算法的确能够有效地解决大规模复杂fjPDPTW，解的质鲞与精确解相当靠近，并且计算时阔大大小予一些常用的启发式算法。这静快速性和可靠性对于实现PDPTW在现实生活中的应用有着重要晌意义。支一．侈一∥一’⋯关键词：车辆调度，‘’———wh-—-一一入算法，局域搜索——一一～—_“’一一f。{，PDPTWr有时间窗口装卸货问题j，庙发式算法，插，～州～ASTUDYoFHEURIS

5、TICALGORITHMSFoRCoMPLEXPDPTWPROBLEMABSTRACTPickupandDeliveryProblemwithTimeWindow(PDPTW)isatypicaloperationsresearchproblemwhichissignificantintheindustryandagriculture，economyfield，transportation，logisticmanagement，resourceallocationfields．TheproblemisalsoatypicalNP-hardproblemincombinatio

6、naloptimization．SoitisatoughandpopularprobleminthefieldofbothoperationalresearchandcombinationaloptimizationDuetothefactthatPDPTWisNP-hardproblem，combinedwiththerealitythatpracticalPDPTWareverylarge，thereisnomuchhopeforfindinganoptimalalgorithminanacceptabletime．Soresearcherputfocusonheuris

7、ticalgorithmpresentlyMyresearchisastudyofheuristicalgorithmstosolvealargecomplexPDPTWwhichincludesmultidepots，multiloadtypeandmaximalworkingtimelimitation．Themaincontributionsareasfollows1．Twoinsertionheuristicmethodsareproposed．OneisbasedonsolomnVRPinse