同时送取货选址路径问题及混合免疫算法

Location-routing problem with simultaneous pickup and delivery and hybrid immune algorithm

研究了同时送取货的选址路径问题(location-routing problem with simultaneous pickup and delivery,LRPSPD),在同时送取货问题中,每个客户都有送货需求和取货需求,并且两种需求需要同时进行服务。在此条件下,建立了以仓库的选址成本、车辆启用成本及运输成本等目标和最小的选址路径模型;针对该模型的特点,设计改进了一种混合免疫优化算法(hybrid immune algorithm,HIA)对该问题进行求解,运用贪心聚类算法生成初始解,利用原始免疫算法对抗体进行评价排序,由邻域搜索操作改进原始算法的免疫操作。最后,通过使用混合免疫优化算法与原始免疫优化算法、模拟退火算法、蚁群算法分别对案例进行求解和对比分析,验证了提出模型的可行性和算法的有效性。

In the simultaneous pickup and delivery problem,every customer has both delivery demand and pick-up demand,and both demands need to be served simultaneously.Under this condition,this paper established a location-routing problem with simultaneous pickup and delivery model to minimize the sum of location cost,routing cost and transportation cost.For solving this model,this paper developed a HIA.It generated the initial solution by greedy clustering algorithm,and evaluated and sorted the antibody by the original immune algorithm.And it improved the immune operation of the original algorithm by the neighborhood search operation.Finally,this paper verified the feasibility of the model and the effectiveness of the algorithm by using the HIA,the original immune algorithm,the simulated annealing algorithm and the ant colony algorithm.