节约里程算法在车辆路径优化中的应用研究

齐建强

【摘 要】 高效地配送会使物流系统的顺利运行得到保障，对配送车辆的路径优化，可以节省配送时间，提高配送的效率，进而提高整个企业的经济效益和社会效益。本文从企业配送货物时，配送车辆存在空载率高、迂回运输现象严重和配送时间长等问题的角度出发，采用节约里程法对车辆路径进行优化。进而提高物流服务水平。

【关键词】 配送路线 车辆路径问题 节约里程法

1 引言

随着我国经济的高速发展，各种工业制造型企业不断发展壮大，市场竞争日趋激烈。企业为了降低成本，提高竞争力，越来越重视物流的发展，物流领域也成为继降低人工、材料费用和扩大销售之后，企业的“第三利润源泉”。在这种大背景的情况下，企业想提高收益，降低物流成本成为企业获取利润的必选之路。对配送线路进行优化对企业乃至对社会都有重大意义，

2 节约里程算法概述

节约里程算法的核心思想是将运输问题中存在的两个回路合并成为一个回路。在上面的合并操作中，整个运输的总运输距离会发生变化，如果变化后总运输距离下降，则节省了运输距离。相应的变化值，叫做节约距离， 如式子所示：。

已知条件：需求点集={1，2，……n}，各个点的需求量为，各点之间的最短距离为。第一步形成一个初始解。确定各车辆配送点集，，……令={j}，j=1，2，……n（先采取单点配送）。第二步，进行节约度的计算，计算所有点对的节约度，然后对计算结果进行升序排列。第三步，进行回路的合并。