1 概述

物流配送路径最短问题是典型的旅行商（Traveling Salesman Problem，TSP）问题。车辆从配送中心出发，将车上货物分别送到本辖区内的其它分发点（简称节点）1,2,3,…,n，车辆在一次配送任务中，只经过各节点一次。由于交通管制和道路方面的原因，可能存在各节点间并不完全互通，个别节点间可能还存在单向性通行，如图1物流配送路线示意图。

对于这样一个典型的TSP问题，随着节点数目的增加，其可能的配送路线数目与节点数目n是成指数型增长的，是一个NP难题，所以很难精确的求出其最优解，因此寻找有效的近似求解算法就具有重要的现实意义。遗传算法是一种仿生算法，核心思想起源于对生物进化过程的认识。通过模仿生物的进化，利用达尔文的进化论和孟德尔遗传变异思想对研究问题进行数学抽象和建模。

遗传算法是通过模仿生物的繁殖、基因变异、物种间竞争和自然选择对研究问题采取适当的计算策略，最终得到研究问题的满意解。遗传算法只利用研究问题的目标满意度评价信息，是一种多条并行的随机搜索优化方法，适用于大规模、高度非线性以及无解析表达式的问题，有很强的通用性[1]。物流配送的路线最短选择问题采用该方法非常合适。

图1 物流配送路线示意图

2 数学建模及求解方法

（1）路线信息。对于从物流配送中心出发，将货物分别投送至各分发点的配送路线之间的关系，可以用表1物流配送节点信息表进行表达（假定11个节点）。对于路线的单向性或节点彼此不通的路线，设值一个比正常路径大几个数量级的值，如表1中设定1 000。……