（ ６）
ｙｉｓ ＝０ 或 １ ｉ，ｊ＝０，１，… ，ｋ； ｓ＝１，２，… ，ｍ
（ ７）
上述 模 型中 ， 配 送 中心 编 号 为 ０， 客 户 点 编号 为 １，２，…，ｋ； ｉ，ｊ 为 客 户 点 序 号 ， ｓ 为 车 辆 序 号 ， ｇｉ 为 客 户 点 ｉ 的 货 运 量 ， ｍ 为
车辆 总 数 ， ｑ 为车 辆 载 重量 ， ｃｉｊ 表 示 点 ｉ 到 点 ｊ 的 运输 成 本 ； ｘｉｊｓ ： 决 策 变 量 ， 表 示 车 ｓ 是 否 由 ｉ 驶 向 ｊ， 如 果 是 ， ｘｉｊｓ 值 为 １， 否
自然选择函数 ｓｅｌｅｃｔｉｏｎ
基因互换， 形成新的基因串。
２．６ 结束条件
交叉函数 ｃｒｏｓｓｏｖｅｒ
当算法的当前进化代数小于预先设定的 Ｎ 时 ， 返 回 ２．２ 节 ， 算 法 继 续。
变异函数 ｍｕｔａｔｉｏｎ
３ 用 Ｍａｔｌａｂ 编程实现遗传算法
３．１ Ｍａｔｌａｂ 函数模块构成
本 文 在 Ｍａｔｌａｂ 环 境 下 编 写 的 遗 传 算 法 程 序 由 一 系 列 完 成 特 定 功 能 的函数组成， 程序的总体框架结构， 即各函数 （ 模块） 的从属调用关 系如图。根据这个图我们依次介绍各个函数。 ３．２ 函数介绍
（ｋ＋ｍ＋１） 维矩阵。矩阵每一行都代表一 个路 径 。计 算适 应 度 函数 由 三 步组 成 ： 第 一步 ， 先 将 已知 给 出 的种 群 与 距离 矩 阵 ｃ 使用
ｆｕｎ 函数一一对应变为成本矩阵 Ｌ， 它的最后一列 ｓｕｍ 为前几项总和。其中的函数结 构为 Ｌ＝ｆｕｎ （ｃ，ｐｏｐ）； ｃ 为 距 离矩 阵 ， ｐｏｐ 为
第 ２９ 卷总第 １３１ 期
·物流商坛·
物流科技
基于 Ｍ/,ａ0ｔ1ｌａ,2ｂ
物流配送路径优化问题遗传算法的实现
Ｔｈｅ Ｒｅａｌｉｚａｔｉｏｎ ｏｆ Ｇｅｎｅｔｉｃ Ａｌｇｏｒ ｉｔｈｍ ｏｆ ＶＲＰ Ｂａｓｅｄ ｏｎ ｔｈｅ Ｍａｔｌａｂ
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
数学 模 型表 示 如 下［１］：
ｋ ｋｍ
""" 目标函数： ｍｉｎＺ＝
ｃｉｊ ｘｉｊｓ
（ １）
ｉ ＝ ０ｊ ＝ ０ｓ ＝ ０
约束条件：
ｋ
"ｇｉ ｙｉｓ ≤ｑ ｓ＝１，２，…，ｍ
（ ２）
ｉ＝０
ｍ
" $ ｙｉｓ ＝
ｉ＝１
１ ｍ
ｉ＝１，２，…，ｋ ｉ＝０
（ ３）
ｋ
"ｘｉｊｓ ＝ｙｊｓ ｊ＝１，…，ｋ； ｓ＝１，２，…，ｍ
仓库， 代表总仓库的 ０ 的数目为 ｍ＋１ 个， 把自然数编码分 为 ｍ 段， 形 成 ｍ 个 子路 径 ， 表 示由 ｍ 辆 车 完成 所 有 运输 任 务 。初始
化 染 色体 时 ， 先 生成 ｋ 个 分 仓库 的 一 个全 排 列 ， 再 将 ｍ＋１ 个 ０ 随 机 插 入 排 列 中 。 注 意 必 须 要 有 ２ 个 ０ 被 分 别 安 排 在 排 列 的 头
弓晋丽， 程志敏 （ 长安大学， 陕西 西安 ７１００６４）
ＧＯＮＧ Ｊｉｎ－ ｌｉ， ＣＨＥＮＧ Ｚｈｉ－ ｍｉｎ （Ｃｈａｎｇ＇ａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｘｉ＇ａｎ ７１００６４， Ｃｈｉｎａ）
摘 要： 在物流管理学中， 研究物流配送路径优化问题 并选取恰当的配送路径， 可以加快对客户需求的响应速度， 提高服务质量， 增强客户对物流环节的满意度， 降低服务商 运 作 成 本 。 但 由 于 物 流 配 送 路 径 优 化 问 题 是 一 个 ＮＰ－ ｈａｒｄ 问 题， 使用传统优化方法很难得到最优解或满意解。本文基于 Ｍａｔｌａｂ 进 行 了 物 流 配 送 路 径 优 化 问 题 遗 传 算 法 的 编 码 ， 利 用 Ｍａｔｌａｂ 强 大 的 数 值 计 算 能 力 较 好 地 解 决 了 这 个 难 题 并 进 行 了 实例验证， 对物流企业实现科学快捷的配送调度和路径的优 化有实际意义。
关键词： 物流配送； 路径优化； 遗传算法； Ｍａｔｌａｂ
中图分类号： Ｕ１１６．２ 文献标识码： Ａ
文章编号： １００２－ ３１００ （２００６） ０７－ ０１０３－ ０３
Ａｂｓｔｒ ａｃｔ： Ｉｎ ｌｏｇｉｓｔｉｃｓ ｍａｎａｇｅｍｅｎｔ ｒｅｓｅａｒｃｈ， ｓｔｕｄｙｉｎｇ ｔｈｅ ｖｅｈｉ－ ｃｌｅ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍ ｃａｎ ａｃｃｅｌｅｒａｔｅ ｔｈｅ ｒｅｓｐｏｎｓｅ ｓｐｅｅｄ ｏｆ ｔｈｅ ｃｕｓｔｏｍｅｒ＇ｓ ｄｅｍａｎｄ， ｉｍｐｒｏｖｅ ｔｈｅ ｓｅｒｖｉｃｅ ｑｕａｌｉｔｙ， ｅｎｈａｎｃｅ ｃｕｓ－ ｔｏｍｅｒ＇ｓ ｓａｔｉｓｆａｃｔｉｏｎ ｉｎｄｅｘ， ａｎｄ ｒｅｄｕｃｅ ｔｈｅ ｂｕｓｉｎｅｓｓ ｓｅｒｖｉｃｅ ｏｐ－ ｅｒａｔｉｏｎ ｃｏｓｔ． Ｈｏｗｅｖｅｒ， ａｓ ａ ＮＰ－ ｈａｒｄ ｐｒｏｂｌｅｍ， ＶＲＰ ｉｓ ｈａｒｄ ｔｏ ｄｒａｗ ａｓ ｓａｔｉｓｆａｃｔｏｒｙ ｃｏｎｃｌｕｓｉｏｎ ｂｙ ｕｓｉｎｇ ｔｒａｄｉｔｉｏｎａｌ ｏｐｔｉｍａｌ ａｌ－ ｇｏｒｉｔｈｍ． Ｔｈｉｓ ｐａｐｅｒ ｍａｋｅｓ ｔｈｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｐｒｏｇｒａｍｍｅ ｆｏｒ ｔｈｅ ＶＲＰ ｂａｓｅｄ ｏｎ ｔｈｅ ｍａｔｌａｂ． Ｔｈｅ ｐｒｏｂｌｅｍ ｉｓ ｐｒｅｆｅｒａｂｌｙ ｓｅｔｔｌｅｄ ａｎｄ ｉｔ ｉｓ ｐｒｏｖｅｄ ｔｈａｔ ｔｈｉｓ ａｒｉｔｈｍｅｔｉｃ ｉｓ ｍｏｒｅ ｅｆｆｉｃｉｅｎｔ ｂｙ ａｎ ｅｘａｍｐｌｅ． Ｉｔ ｍａｙ ｂｅ ｕｓｅｆｕｌ ｆｏｒ ｔｈｅ ｃｏｍｐａｎｙ ｔｏ ｍａｎａｇｅ ｔｈｅ ｐｈｙｓｉｃａｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｓｃｉｅｎｔｉｆｉｃａｌｌｙ ａｎｄ ｔｏ ｏｐｔｉｍｉｚｅ ｔｈｅ ｄｉｓ－ ｔｒｉｂｕｔｉｏｎ ｒｏｕｔｉｎｇ ｓｕｃｃｅｓｓｆｕｌｌｙ． Ｋｅｙ ｗｏｒ ｄｓ： ｐｈｙｓｉｃａｌ ｄｉｓｔｒｉｂｕｔｉｏｎ； ｒｏｕｔｉｎｇ ｏｐｔｉｍｉｚｉｎｇ； ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ； Ｍａｔｌａｂ
主 函 数 ｇａ， 其 函 数 结 构 为 ： ｆｕｎｃｔｉｏｎ ［Ｂｅｓｔｐｏｐ， ｂｅｓｔ， ｔｒａｃｅ， ＭＩｎｚ，
染色体交叉函数 ｉｎｔｅｒｃｒｏｓｓ
删除函数 ｄｅｌ 调整函数 ａｄｊｕｓｔ
Ｍｅａｎｚ］＝ｇ（ｎｕｍ， ｋ， ｍ， Ｎ， ｃ， ｇ， ｑ， ｐｍｕｔａｔｉｏｎ， ｐｃｒｏｓｓ）。Ｍａｔｌａｂ 以 矩 阵 为 基
下， 达到使路程最短、费用最少、时间尽量短， 使用车辆尽量少等目标。ＶＲＰ 问题被证明为是一个 ＮＰ－ ｈａｒｄ 问 题。国 内 外 不少
学者已经证明使用遗传算法在求解 ＶＲＰ 问题时， 具有巨大的优越性［１］。
Ｍａｔｌａｂ 功能强大， 利用 Ｍａｔｌａｂ 矩阵运算的强大功能来编写遗传算法程序有着巨大的优势， 但由于用遗传算法求解 车 辆 路径
物流配送路径优 化问 题 ， 即 所谓 的 车 辆路 径 问 题 （ Ｖｅｈｉｃｌｅ Ｒｏｕｔｉｎｇ Ｐｒｏｂｌｅｍ） ， 一 般 定 义为 ： 对 一 系列 发 货 点和 收 货 点， 组
织适当的车辆行使路线， 在满足货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制和时间限制等的约束条件
（ ４）
ｉ＝０Biblioteka 收稿日期： ２００５－ １２－ ２２ 作者简介： 弓晋丽（ １９８３－ ） ， 女， 山西文水人， 长安大学汽车学院硕士研究生， 研究方向： 物流系统， 道路运输与枢纽规划。
·１０３·
物流科技
! 物流商坛 !
ｋ
"ｘｉｊｓ ＝ｙｉｓ ｉ＝０，１，…，ｋ；
（ ５）
ｊ＝０
ｘｉｊｓ ＝０ 或 １ ｉ，ｊ＝０，１，…，ｋ； ｓ＝１，２，…，ｍ
２．４ 交叉算子
本文构造交叉算子为： 如果染色体交叉点处的两个基因都为 ０， 则
将每一个染色体的交叉段移到对方染色体的首部得到新的染色体； 如 果染色体交叉点处的基因不全为 ０， 则将交叉点左移 （ 右移） ， 直到左
初始化函数 ｉｎｔｉａｌｉｓｅ
右两个交叉点处的基因都为 ０， 再进行以上运算， 削去相同的元素， 再 调整形成两个合法的个体基因串。对交叉成功所获得的子代应用 （ ７）
色体的目标值。最后 计 算 染色 体 适 应度 的 概 率分 布 ： Ｐｉ ＝ｆ／∑ｆ 其中 Ｐｉ 表 示 第 ｉ 条 染 色 体的 适 应 度概 率 分 布， ｆｉ 表 示 第 ｉ 条染 色 体
的适应度。
２．３ 自然选择
计算父代和子代的适应度， 选择父代和子代中性能最优的染色体进入种群， 其它的染色体采用轮盘赌选择方法来确定。
ｎｕｍ： 种群规模； ｋ： 分仓库数； ｍ： 车辆数； Ｎ： 迭代次数； ｃ： 距离矩阵； ｇ： 各客户点需求矩阵； ｑ： 最 大 载重 量 ； ｐｍｕｔａ－
ｔｉｏｎ： 变异概率； ｐｃｒｏｓｓ： 交叉概率。
初始化函数 ｉｎｔｉａｌｉｓｅ， 函数结构为： ｆｕｎｃｔｉｏｎ ［ｐｏｐ］＝ｉｎｔｉａｌｉｓｅ （ｎｕｍ，ｋ，ｍ）。入口参数 ｎｕｍ， ｋ， ｍ 与主函数保持一 致 ， ｐｏｐ 为 ｎｕｍ＊
计算成本函数 ｆｕｎ
式求得其对应的适应值， 并与其父代进行比较， 选择四者中性能最好 的 ２ 个进入种群。
计算目标值函数 ｃｏｕｎｔｚ
２．５ 变异算子 同现实情形相同， 以一定的变异率随机选取发生变异的个体染色
主函数 ｇａ
适应度值计算函数 ｆｉｔ
体， 然后在该染色体上随机选取两个非零基因位， 把这两个位置上的
一种群。第二步， 由上步得到的 Ｌ 矩阵 根 据 式 （ ８） 使 用 函 数 ｃｏｕｎｔｚ 计 算 得 到目 标 值 。目标 值 计 算函 数 ｃｏｕｎｔｚ 函 数结 构 为 ｆｕｎｃ－
问 题 时有 约 束 条件 的 限 制， 很 难 用 一 般 的 Ｍａｔｌａｂ 遗 传 算 法 工 具 箱 实 现 。 本 文 基 于 车 辆 路 径 问 题 约 束 条 件 的 特 殊 性 ， 采 用 改 进