送货路线-数学建模-一等奖.pdfVIP

摘 要 摘 要 本文讨论了送货员送货路线的优化设计问题 , 即在给定送货地点和给定 设计规范的条件下，综合考虑最大载重范围、 最大带货体积以及各货物送货时限， 确定业务员的最佳运行路线策略 .并总结出一些在这类图中求解近似最优回路的 有效法则 . 对于问题 1，采用了两种方法进行了计算，第一种是通过 Floyd 算法做出各 顶点间的最短路径矩阵，然后选出 1~30 号货物所送达的顶点间的最短路径及距 离，用二边逐次修正法求解 Hamilton 圈；第二种是通过蚁群算法获得多条近似 优解，选取最佳线路 . 对于第二问，则采用改进的遗传算法，求解有时间约束条件的 TSP 问题， 根据线路规划问题的特点，基于遗传算法（ GA ）建立了一个适用于带有时间约 束的送货路线规划模型 .实验证明了此算法的有效性和可行性 . 对于第三问，利用分割求解法和蚁群算法的合成算法， 运用共同链分割全图， 对每一个分图进行最优求解，由此得到全图的最优解。 关键词 送货问题；优化路线； TSP 模型；蚁群算法 1 送货路线设计的数学模型 1 问题重述 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业 也渐渐兴盛， 每个送货员需要以最快的速度及时将货物送达， 而且他们往往一人 送多个地方，请设计方案使其耗时最少 . 现有一快递公司， 库房在图 1 中的 O 点，一送货员需将货物送至城市内多处， 请设计送货方案， 使所用时间最少 .该地形图的示意图见图 1，各点连通信息见表 3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线 .各件货物的相 关信息见表 1，50 个位置点的坐标见表 2. 假定送货员最大载重 50 公斤，所带货物最大体积 1 立方米 .送货员的平均速 度为 24 公里/小时 .假定每件货物交接花费 3 分钟，为简化起见， 同一地点有多件 货物也简单按照每件 3 分钟交接计算 . 现在送货员要将 100 件货物送到 50 个地点 .请完成以下问题 . 1. 若将 1~30号货物送到指定地点并返回 .设计最快完成路线与方式 .给出结果 . 要求标出送货线路 . 2. 假定该送货员从早上 8 点上班开始送货，要将 1~30 号货物的送达时间不 能超过指定时间，请设计最快完成路线与方式 .要求标出送货线路 . 3. 若不需要考虑所有货物送达时间限制 (包括前 30 件货物 ) ，现在要将 100 件 货物全部送到指定地点并返回 .设计最快完成路线与方式 .要求标出送货线路，给 出送完所有快件的时间 . 由于受重量和体积限制，送货员可中途返回取货 .可不考 虑中午休息时间 .. 2 模型的假设与符号说明 2 2.1 模型假设 1．假设送货员只能沿如图所示连通线路行走，而不能走其它任何路线；