基本信息
- 项目名称：
- 物流配送的路径优化与车辆调度系统设计
- 来源：
- 第十二届“挑战杯”省赛作品
- 小类：
- 机械与控制
- 大类：
- 科技发明制作B类
- 简介：
- 车辆路径问题是物流管理领域关注的热点和难点问题之一。如何合理地安排车辆、行车路径和出行时间，以最低成本将货物准时送达客户，实现物流配送系统高效低成本地运作，这是多年来困扰学术界和产业界的难题。本研究针对物流配送路径优化与车辆调度问题进行了较全面的分析和研究，针对小规模物流配送问题，在求解过程中，采用C-W节约算法并设计了适用该算法的软件，较好地解决了小规模配送中的路径优化和车辆调度问题。
- 详细介绍：
- 物流配送是物流活动中直接与消费者相连的环节。在物流的各项成本中，配送成本占了相当高的比例。因此，采用科学合理的方法来进行配送路径选择和车辆调度，是物流配送中非常重要的一项活动。 物流配送路径优化与车辆调度问题，可以归结为对于一系列配送点，如何组织合适的行车线路，使配送车辆有序地通过它们，在满足货物配送量、车辆容量限制、行驶里程限制、时间限制的情况下，达到里程最短，费用尽量少，时间尽量少，用车数量尽量少几个目标。在本文中，首先分析了物流业、配送业的发展现状，进而引出配送路径优化与车辆调度问题，在对此问题进行了分析和分类之后，针对城市小规模物流配送问题，采用C-W节约算法构建数学模型，并对该算法进行了计算机编程，实现了对该问题的快速处理和计算机实现，同时该软件运行速度快、计算精确、占用系统资源少，是解决该问题的有效途径。将此软件应用于中小型物流企业可以为企业带来可观的经济效益和社会效益，具有十分广阔的市场前景。
作品专业信息
设计、发明的目的和基本思路、创新点、技术关键和主要技术指标
- 在城市配送业务中，配送线路安排的合理与否对配送速度、成本、效益影响很大，特别是多用户配送线路的确定更为复杂。采用科学、合理的方法来进行配送线路优化，是物流配送中非常重要的一项活动。本作品设计的主要目的就是解决小规模物流配送的路径优化与车辆调度问题，为多个用户的配送问题确定合理的配送方案，节约配送成本，提高配送效率，并设计软件对该问题的计算实现计算机的快速处理。 设计的基本思路是首先分析物流业、配送业的发展现状，引出配送路径优化与车辆调度问题，在对此问题进行了分析和分类之后，针对小规模物流配送问题的特点，在求解过程中，应用C-W节约算法寻找最优路径和配送方案，并运用计算机编程语言设计适用该算法的操作软件，通过运行软件实现对该问题的快速处理并得到最佳的优化方案。 该设计的创新点和技术关键：应用C-W节约算法处理小规模物流配送问题，该方法针对性强，运算思路思路清晰明了，精确度高，计算时间短。运用计算机软件实现了该问题的快速准确处理。避免了人工计算可能出现的错误和低效率。 主要技术指标：本软件的开发平台是VB6.0，该平台兼容性好，以Windows XP为操作系统，适用性强，运算速度<1秒,运行时所占用的内存和虚拟内存仅为10.82MB和 5.61MB,软件占用磁盘空间仅为2.67MB, 经过五十余次算例验证，运算精度可接近百分之百。
科学性、先进性
- 由一个配送中心和多个零售商组成的分布式二级供应链中，配送车辆路线安排问题十分复杂，精确算法的计算量太大，需要采用启发式算法，节约法是一种常见的启发式算法，它运用一些经验法来降低优化模型的精确程度，并通过模仿人的跟踪校正过程，来求得运输路线的满意解（不一定是最优解）。 本研究在解决配送路径和车辆调度问题时所采用的C-W节约算法是根据物流中心的运输能力和物流中心到各送/取货点以及各个送/取货点之间的距离，制定是总的车辆运输吨公里数最小的方案。 本作品中所设计的软件在城市小规模配送（3-50个配送点）中优势明显，操作界面清晰明了、简单快捷，特别适合于运输距离近、批量小的配送问题，如超市连锁，或者同种货物、多客户的情况，如乳制品的配送物流。
获奖情况及鉴定结果
- 本作品曾在大连交通大学2010年5月份举办的大连交通大学学生物流设计大赛中获得一等奖。
作品所处阶段
- 中试阶段。
技术转让方式
- 无
作品可展示的形式
- 本作品中的软件可以现场运行演示。
使用说明,技术特点和优势,适应范围,推广前景的技术性说明,市场分析,经济效益预测
- 使用说明：输入配送点的个数、各个配送点之间的距离、各点的需求量、运输车辆的容量和行驶里程限制，即可显示运算结果。 主要优势在于：针对小规模问题设计，运算速度快方案结果准确度高，占用计算机系统资源量小，对软硬件要求低。 技术说明：开发平台是VB6.0，该平台兼容性好，无需额外安装其他软件环境，界面简洁明了，所占空间小，便于携带。以Windows XP为操作系统，适用性强。使用了spread软件完善了界面，使之更加清晰有层次。 市场分析和经济效益预测：现代社会物流配送业高速发展，客户对配送的要求也日益提高，设计合理的配送路径和车辆调度方案能够降低配送的成本、提高配送的效率和客户满意度，因此对从事物流配送的企业来说拥有自己的配送系统对配送业务进行优化是未来的发展趋势。本作品中的软件是针对城市小规模配送专门设计的，应用简单，针对性较强，应用于中小型物流企业可以为企业可以节约大量配送成本，带来可观的经济效益和社会效益，具有十分广阔的市场前景。
同类课题研究水平概述
- 一、目前国内外学者研究的有以下几种模型：（1）带车辆容量约束的单车场VRP（2）带时间窗的车辆路径问题VRPTW（3）车型车辆路径问题MFVRP/HFVRP（4）多车场车辆路径问题MVRP（5）带回程运输的车辆路径问题VRPB（6）分割送货车辆路径问题VRPSD（7）开放式车辆路径问题OVRP（8）随机需求车辆路径问题VRPSD（9）动态随机车辆路径问题VRPDS（10）多目标的车辆路径问题MVRP。 二、国内外车辆调度模型求解算法研究现状：求解物流配送车辆调度问题的方法可以分为精确算法和启发式算法两大类。精确算法指可求出其最优解的算法，主要有：(1)分枝定界算法 (2)K阶中心树和相关算法 (3)动态规划法 (4)集分割和列生成法 精确算法基于严格的数学手段，在问题可求解的情况下，计算结果优于启发式算法，但由于无法避免计算量的指数爆炸问题，精确算法只能有效地解决小规模的VRP，各算法所适用的问题特点也不同。 启发式算法是在状态空间中的改进搜索算法，它对每一个搜索位置进行评价，得到最好的位置，再从这个位置进行搜索直到目标。由于VRP是强NP难题，高效的精确算法存在的可能性不大，为此要构造高质量的启发式算法。现有文献中提出的启发式算法有以下几类：(1)Clarke-Wright节约算法 (2)Sweep算法（3) 两阶段算法 (4)禁忌搜索 (5)模拟退火算法 (6)遗传算法 (7)蚁群算法。 三、国内相关软件发明专利情况：国内现有一种物流配送车辆路径优化方法专利（CN101739812A），包括下述步骤：步骤1，参数设置及初始化；步骤2：若Nc≤Nmax，判断迭代次数是否达到最大迭代次数，如果是，就结束循环，执行步骤7；否则，执行步骤3；步骤3，并购操作，再对物流配送路径进行调整操作；步骤4，重组操作，插入操作，调整操作；步骤5，成本评估；步骤6，选择最优物流配送路径方案；步骤7，获得最优物流配送车辆路径方案。此方法通过抽象企业并购行为，由并购操作，重组操作等组成的并购方法，提高物流配送路径优化的收敛性，可以高效地得到最优物流配送路径方案。 该方法主要针对配送点特别多的大规模物流配送。运算量大占用系统资源多，并且需要人为调整。对中小规模的配送路径规划和车辆调度问题不适用。
