系统表示层由窗体组成，包括登录窗体、客户管理窗体、智 能配送窗体等。
系统功能层是建立在数据库之上，应用程序通过这层访问 数据库，封装了对数据库的增、删、改、查询等操作。
系统数据层是系统的最底层，它存储系统的所有数据。 ２．２系统功能模块划分和具体描述
系统功能模块划分示意图如图２所示。 ２．２．１用户登录
在研究自然界中生物的遗传和进化现象时。生物学家使用 适应度这个概念来度量某个物种对于其生存环境的适应程度。
对生存环境适应程度较高的物种将有更多的繁殖机会；而对生 存环境适应程度较低的物种，其繁殖机会就相对减少，甚至会 逐渐灭绝。与此类似，遗传算法中也使用适应度这个概念来度 量群体中各个个体在优化计算中有可能达到或接近于或有助 于找到最优解的优良程度。适应度较高的个体遗传到下一代的 概率就较大；而适应度较低的个体遗传到下一代的概率相对小
算工程等；谷文祥（１９４７一），男，教授，博士生导师，研究方向：智能规划与规划识别等。
万方数据
２００
２００７，４３（６）
Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用
Ｉ用户登录ｌ
Ｉ
客户
ｌ配送人员Ｉ 系统管理员ｌ
１Ｌ
Ｊ
上
＼．ｊ．／ Ｉ提交需求Ｉ ｌ智能配送ｌ Ｉ系统维护ｌ
目标函数中的Ｇ为从客户ｉ到客户ｊ的费用成本，它包 括：（１）车辆成本；（２）人员成本；（３）配送延迟成本。Ｇ为配送 中心存储的基础数据，是配送中心建立的包含路线，路况，距离 等基本数据库，根据基本数据库预先计算出各客户和配送中心 之间的运输成本。基本数据库可以不断增加．修改和完善。配送 时只要输入客户的相关信息，即可实现自动调度。
摘 要：为提高中小型物流企业在市场中的竞争能力。文章提出了基于遗传算法的智能化解决方案。文章论述了基于遗传算法的 物流车辆配送系统的设计与实现，详细阐述了基于自然数编码的遗传算法在物流车辆调度中的运用等关键技术。通过模拟测试， 效果良好。系统适合于任何中小型物流公司用于调度车辆来实现智能化配送。 关键词：遗传算法；车辆调度系统；自然数编码 文章编号：１００２—８３３１（２００７）０６—０１９９—０４ 文献标识码：Ａ 中图分类号：ＴＰ３９１．９
合，扛｛１，２…，ｎ），ｉ∈，，ｋ∈Ｋ。
万方数据
目标函数满足的约束条件为：
÷ ｆｍ（ｉ＝Ｏ）
（ｉ）
鲁砌一１１（ｉ＝１，２。…，ｎ） （２）
上式中（１）控制ｎ个客户由ｍ辆车来共同完成，（２）控制
每一客户只有一辆车来完成。此函数用来满足约束条件（１）。
约束条件中的
。，ｆｌ（车辆ｋ为客户ｉ服务） （３） ““【０（车辆ｋ不为客户ｉ服务） （４）
２系统的总体设计思想 ２．１ 系统的架构设计
系统采用基于ＸＭＬ Ｗｅｂ Ｓｅｒｖｉｃｅｓ的三层Ｃ／Ｓ结构。这三 层结构分别为：数据层（数据库服务器层）：实现数据的集成；功
能层（运用服务器层）：实现数据的发送与处理；表示层（客户机 层）：实现数据的显示。这三层结构组成如图１所示。
图１基于ＸＭＬ的三层Ｃ／Ｓ结构
Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用
２００７，４３（６）
１９９
基于遗传算法的物流配送系统的设计与实现
谭前进，林和平，谷文祥 ＴＡＮ Ｑｉａｎ—ｊｉｎ，ＬＩＮ Ｈｅ－ｐｉｎｇ，ＧＵ Ｗｅｎ－ｘｉａｎｇ
东北师范大学计算机学院，长春１３０１１７
Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｏｆ Ｎｏａｈｅａｓｔ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｃｈｕｎ １３０１ １７，Ｃｈｉｎａ
智能配送前，系统先扫描客户的需求量．有超过车辆载量 的。先看客户的需求能装满几辆车，直接从可供选择的车辆中 随机挑选几辆车去完成该客户的需求，然后把装不满一辆车的 需求量作为该客户新的需求量去参与遗传算法的运算。
文中所构造的目标函数比较简单，约束条件也极少，主要 考虑到实际运用中一般目标函数比较复杂．约束条件较多，很 难用较简单的数学公式来描述问题的具体解，即使可以数学建 模，用计算机实现时难度也相当的大．文中尝试采用一种简化 的思维来解决实际的问题。由于程序设计时，很多约束条件可 以人为的控制，文中尝试在程序设计中控制所有的约束，并把 所有的约束转化到最小费用的目标函数中，通过改变染色体的 适应度值来满足该模型中的所有约柬条件。初始建模时，可以 不考虑这些约束条件，贝｜ｊ建立起来的数学模型就相对的简单和 实用．使用遗传算法初始化群体时，也相对会产生一些无效解， 在产生无效解后需要对这些无效解进行调整，相应的在进行遗 传算法进化时可能需要更多的空间和时间来进化才能得到最 优解或近似最优解。文中所采用的是用”计算机的时间和空间 代价”来换取实际问题能简单实现的思想。
Ｅ－ｍａｉｌ：ｔａｎ嘶６１５＠ｎｅｎｕ．ｅｄｕ．ｃｎ
ＴＡＮ Ｑｉａｎ－ｊｉｎ，ＬＩＮ Ｈｅ－ｐｉｎｇ，ＧＵ Ｗｅｎ－ｘｉａｎｇ．Ｄｅｓｉｇｎ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｌｏｇｉｓｔｉｃｓ ｖｅｈｉｃｌｅｓ ｄｉｓｐａｔｃｈｉｎｇ ｓｙｓｔｅｍ ｂａｓｅｄ ｏｎ ＧＡ．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ，２００７，４３（６）：１９９—２０２．
≈
目标函数中的艺只（￡。）为惩罚函数，当车辆不能按时到达
“；，
时，引入此函数来增加车辆调度的成本。在计算机中实现时，该
值设为足够大就行。艺Ｐｉ（ｔ。）惩罚函数是用来满足约束条件
‘Ｅ，
（３）和（４）。 目标函数中的Ｐｎｕｍ（Ｍ）为车辆装载容量约束，若违反该
约束，则将Ｐｎｕｍ（Ｍ）值选择为一无穷大的正数，使配送成本增 加到不能容忍的程度，考虑到采用计算机实现，为防止溢出ｕｍ（Ｍ）用来满足约束条 件（２）。
１ 引言 在竞争日益激烈的现代商业信息社会．企业只有以市场为
核心去适应不断变化的环境并及时对市场做出反应．才能在竞 争中立于不败之地。物流管理正是以实现上述要求为目标。合 理使用调度运输工具，优化运输路线，降低企业物流成本，是物 流管理的重要功能【４ｌ。由于对物流管理中的车辆调度问题的研 究对社会经济发展具有举足轻重的作用，因此，国内外学术界 对物流运输系统的调度优化问题十分关注，研究的也比较早， 但大部分都是理论上的跟踪型研究，真正为物流企业解决实际 问题软件产品却非常少。因此．利用Ｖｉｓｕａｌ Ｃ＋＋．ＮＥＴ和ＡＤＯ． ＮＥＴ访问数据库的技术设计并开发了基于遗传算法的物流车 辆配送系统。通过系统，保证了调度的合理性．降低了运输成 本．更能适应现代化的物流企业管理。本系统是东北师范大学 计算机学院开发的物流信息管理系统项目的深入研究和开发． 通过模拟测试，效果良好。
系统用户包括配送工作人员、客户、系统管理员三类．进入 系统前需输入用户名和密码登录验证身份，当验证正确后则进 入该用户权限范围内的操作界面。 ２．２．２用户提交需求
该模块管理用户当天向系统所提交的需求信息。
基金项目：国家自然科学基金（ｔｈｅ Ｎａｔｉｏｎａｌ Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｆｏｕｎｄａｔｉｏｎ ｏｆ Ｃｈｉｎａ ｕｎｄｅｒ Ｇｒａｎｔ Ｎｏ．６０４７３０４２；６０５７３０６７）。 作者简介：谭前进（１９８０一），男，硕士生，研究方向：并行计算，ＥＲＰ软件开发等；林和平（１９５６一），男，教授，硕士生导师，研究方向：计算机图形学、计
一些，度量个体适应度的函数称为适应度函数。
文中适应度函数定义如下：
Ａｂｓｔｒａｃｔ：Ｆｏｒ ｉｍｐｒｏｖｉｎｇ ｔｈｅ ｃｏｍｐｅｔｉｔｉｖｅ ａｂｉｌｉｔｙ ｏｆ ｍｅｄｉｕｍ ａｎｄ ｓｍａｌｌ－ｓｉｚｅ ｌｏｇｉｓｔｉｃｓ ｅｎｔｅｒｐｒｉｓｅ ｉｎ ｍａｒｋｅｔ，ａ ｉｎｔｅｌｌｉｇｅｎｔ ｓｏｌｕｔｉｏｎ ｂａｓｅｄ ｏｎ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｉｓ ｐｕｔ ｆｏｒｗａｒｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ．Ａｎｄ ｔｈｅ ｄｅｓｉｇｎ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｌｏｇｉｓｔｉｃｓ ｖｅｈｉｃｌｅｓ ｄｉｓｐａｔｃｈｉｎｇ ｓｙｓｔｅｍ ｂａｓｅｄ ｏｎ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｉｓ ｄｉｓｃｕｓｓｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ，Ａｔ ｔｈｅ ｓａｍｅ ｔｉｍｅ ｔｈｅ ｋｅｙ ｔｅｃｈｎｏｌｏｇｉｅｓ ｓｕｃｈ ａｓ ｔｈｅ ｉｍｐｌｅｍｅｎｔｉｎｇ ｏｆ ｔｈｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｎａｔｕｒａｌ ｎｕｍｂｅｒ ｅｎｃｏｄｅ ｉｎ ｔｈｅ ｌｏｇｉｓｔｉｃｓ ｖｅｈｉｃｌｅｓ ｄｉｓｐａｔｃｈｉｎｇ ｈａｖｅ ｂｅｅｎ ｅｘｐｏｕｎｄｅｄ．Ｂｙ ｓｉｍｕｌａｔｉｖｅ ｔｅｓｔｉｎｇ，ｗｅ ｇｅｔ ｇｏｏｄ ｅｆｆｅｃｔ．Ｓｏ ｔｈｉｓ ｓｙｓｔｅｍ ｓｕｉｔｓ ａｎｙ ｍｅｄｉｕｍ ａｎｄ ｓｍａｌｌ－ｓｉｚｅｄ ｌｏｇｉｓｔｉｃｓ ｅｎｔｅｒｐｒｉｓｅ ｄｉｓｐａｔｃｈｉｎｇ ｖｅｈｉｃｌｅ ｔｏ ｉｍｐｌｅｍｅｎｔ ｉｎｔｅｌｌｉｇｅｎｔ ｄｉｓｔｒｉｂｕｔｉｏｎ． Ｋｅｙ ｗｏｒｄｓ：ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ；ｖｅｈｉｃｌｅｓ ｄｉｓｐａｔｃｈｉｎｇ ｓｙｓｔｅｍ；ｎａｔｕｒａｌ ｎｕｍｂｅｒ ｅｎｃｏｄｅ
谭前进，林和平，谷文祥：基于遗传算法的物流配送系统的设计与实现
２００７，４３（６）
２０１
送中－ｔｋ，的序号为０，依次对各配送点编号形成染色体，该染色
体表示了车辆调度，路线安排等各种信息。例如。染色体 ０１２０３４５０表示一条路线从配送中心出发，经过配送点１。２后 回到配送中心；另一条路线从配送中心出发，经过配送点 ３。４，５回到配送中心。 ４．２定义适应度计算函数
系统管理员拥有最高权限，可以对系统进行维护，包括对 客户和用户进行管理。为安全起见，所有对系统的操作都存在 系统日志．眦文本文件中，可供查看。
３车辆调度模型 物流车辆调度路径优化问题最早是在１９５９年由Ｄａｎｔｚｉｇ
和Ｒａｍｓｅｒ首先提出的．即所谓的车辆调度问题（Ｖｅｈｉｃｌｅ Ｒｏｕｔｉｎｇ Ｐｒｏｂｌｅｍ简称ＶＲＰ）。它也是目前在物流系统中最受关 注的一个闻题之一。ＶＲＰ问题定义为：运输车辆从一个或多个 设施到多个地理上分散的客户点．优化设计一套车辆调度的方 案，同时要满足～系列的约束条件，该问题的前提是设施位置， 客户点位置和道路情况已知，由此设计一套车辆调度方案。以 满足目标函数［２１。需要满足的约束条件是：