论文部分内容阅读
配送是物流活动中直接与消费者相连的环节。在物流的各项成本中,配送成本占了相当高的比例。配送线路合理与否对配送速度、成本、效益影响很大,特别是多用户配送线路的确定更为复杂。因此,车辆线路安排问题(Vehicle Routing Problem,简记VRP)成为众多学者竞相研究的热门话题。在高度发展的商业社会中,消费者对时间的要求越来越严格,以往的到货“日”已转换成到货“时”,特别是随着Internet的普及和电子商务的发展,传统的VRP算法已无法应付快速回应(Quick Response)顾客需求对物流配送提出的要求,于是时间窗的概念应运而生。带有时间窗的车辆调度问题是比VRP复杂程度更高的NP难题,以往的学者多致力于启发式算法的研究。启发式算法虽能快速求解大型问题,但对解的质量没有保证。 本文针对有时间窗的车辆调度问题,建立了含有时间惩罚函数的数学模型,并将之分解为分群主问题和巡回子问题两个求解过程。在第一阶段,先利用遗传算法对顾客进行分群。第二阶段针对每一顾客群,用节约法找出车辆最佳的巡回路线,再将第二阶段获得的巡回结果反馈到第一阶段,作为分群遗传算法的适应值。经过多次迭代反复这一过程,最后得到一个满意的车辆调度结果。本文设计的二阶段混合遗传算法在求解时间和效果上表现出良好的性能,尤其是求解大规模的车辆调度问题,具有一定的实际应用价值。