宋 娟，崔 艳

（1.宁夏大学 物理电气信息学院，宁夏 银川 750021；2.河南广播电视大学 理工学院，河南 郑州 450008）

0 引言

电子商务与连锁商业的兴起推动了物流业的发展[1]，近年来同城快递配送问题已经成为现代物流系统中微观层次的热点问题[2]。

目前，基于同城快递配送方案的研究多集中在算法优化上，遗传算法在求解组合优化问题[3-4]上所表现出的良好特性，被广泛地应用于快递配送领域。本文针对传统遗传算法的收敛慢、全局搜索能力差等不足，提出了一种改进的遗传算法。该算法采用了2-OPT(2-optimization)与翻转变异相结合的变异方法，并结合了模拟退火机制[5]，经实验验证，在解决同城快递配送问题方面有较高的效率。

1 快递配送问题的建模

1.1 快递配送问题的描述

同城快递配送问题可描述如下：某快递公司要从一个配送中心向若干个配货点配送快递，配送中心拥有若干辆配送车辆，每辆车的承重量相同并已知，选取的车辆数和每辆车的路线是未知的。配送车辆从该中心出发，在车辆负载范围内进行配送，并在任务完成后返回配送中心，如图1所示是4条车辆行驶路线的配送图。本文采用车队行驶的总距离衡量快递配送的代价。总距离越小，表明配送方案越优。

图1 车辆行驶路线的配送图

1.2 快递配送问题的数学模型

以最短配送距离为目标，针对同城快递问题，建立数学模型。模型中，配送中心编号为0，快递提货点编号为 1，2，…，n，配送中心和客户点均用 i(i=0，1，2，…，n)来表示，cij表示从客户i到客户j的运输成本（这里指距离），xijk表示车辆 k从 i到 j，yik表示需求点 i由 k服务，如式(1)、(2)所示。……