车辆调度之车辆调度问题

物流人工智能技术技能培训项目三人工智能算法在配送环节应用任务七车辆调度之车辆调度问题目录CONTENTS车辆调度的优化目标PART1配送车辆优化调度的模型PART2车辆调度问题算法的分类PART3智能算法在物流配送车辆路径问题中的应用PART4【教学目标】过程与方法：知识与技能：1.掌握车辆调度的优化目标；2.了解配送车辆优化调度的模型；3.熟悉车辆调度问题算法的分类。在学习动画视频的过程中，理解其基本工作原理，了解其实际应用价值。情感、态度与价值观：1.提升对人工智能的认识，发展辩证思维，客观认识人工智能技术对社会的影响，培养正确的科学技术应用观。2.坚定拥护中国共产党领导和我国社会主义制度。车辆调度问题：根据发货点以及接收点，组织适当的运输路线，当车辆到达目的地时，它可以满足规定的限制，又能达到最终目标（如最短的配送距离、最少的配送车辆数量、最低的配送价格、最低的劳动消耗、最短的花费时间等）。车辆调度问题（VRP）由Dantzig和Ramser首次提出后，便引起了运筹学、数学、计算机等各大领域学者的极大重视。建立合理的配送方案可以有效缩短物流配送过程中的交货时间，大大提高配送效率以及经济效益，因此，车辆调度问题的研究对降低物流配送成本、实现合理的物流管理具有重要作用。一、车辆调度的优化目标车辆调度问题是在满足一定约束条件下，选择某种目标作为优化目标，实现总配送成本（广义的配送成本，如配送时间、总费用、需要车辆等）最优。其中总配送成本一般表现为最小化总费用，即车辆完成配送任务的各项费用之和最小，如车辆启用固定费用、车辆行驶费用、车辆等待费用、车辆服务费用、车辆惩罚费用等；最小所需车辆数即完成全部配送任务所需总车辆数最小；最小总距离即完成全部配送任务车辆路径总长度最小；最短服务时间即完成全部配送任务总配送时间最小，配送时间一般包括车辆行驶时间、等待时间、服务时间和延误时间等。二、配送车辆优化调度的模型通过建立数学模型来定量研究物流配送成本的方法，目前可以归纳为三类：物流配送车辆调度问题数学模型可描述为：车辆由配送中心发出，对每一个客户按照时间或其它要求配送到，车辆完成配送后返回配送中心，规定每个客户只能由一辆车对其进行服务且只服务一次，要求在满足约束条件（如载重约束、时间约束、里程约束等）下对车辆行驶路径进行优化，使完成配送的优化目标（成本、路程、车辆数等）最小。物流车辆调度问题的数学模型是目标规划模型，其结构特征一般为：minormaxz=f(x)物资流模型集覆盖模型车辆流模型2.1有载重约束的车辆调度模型车辆调度问题根据载货任务情况可分为非满载车辆调度问题以及满载车辆调度问题。非满载车辆调度问题要求每个客户需求量少于车辆载重量，一辆车能够同时给一个或多个客户运送货物。大多数时候一次任务不能恰好装满整车，这往往造成车辆装载率不高。满载车辆调度问题中，客户需求不小于车辆载重量，完成每次任务都需要满载行驶，配送过程需要多辆车满载，存在着最后一辆车非满载的情况。目前，对于车辆调度问题的研究以非满载车辆调度问题为主。首先，给出决策变量：二、配送车辆优化调度的模型下面对非满载车辆调度问题建立车辆调度模型。其中：F为车辆固定费用，m为车辆数，cijk为单位里程成本，dij为客户i到客户j的距离，qi为客户需求量，Q为车辆载重量，Lk为车辆最大行驶距离；式（2）是载重约束，式（3）是每个需求客户由一辆车来完成，式（4）是车辆最大行驶距离限制，式（5）表示每个客户都能得到车辆的配送任务，式（6）、式（7）表示两个变量之间的关系，式（8）、式（9）表示决策变量为0-1约束。（1）（2）（3）（4）（5）（6）（7）（8）（9）二、配送车辆优化调度的模型2.2有时间约束的车辆调度模型时间约束问题可分为硬时间窗约束、软时间窗约束、混合时间窗约束三种。硬时间窗问题惩罚函数设置：车辆必须在[ei，li]时间内到达，否则给予其较大惩罚值M。下面建立带硬时间窗约束的车辆调度模型需添加时间窗约束方程式：其中：ti为配送车辆到达客户i的时间，Ti为在客户i处装卸货所耗费的时间，tij表示车辆从i到j所用的时间，T为一足够大的常数。（10）（11）（12）二、配送车辆优化调度的模型三、车辆调度问题算法的分类依据求解VRP问题方法的不同，将算法分为两大类，分别是：启发式算法精确算法分枝定界法割平面法网络流算法动态规划法启发式算法三大类经典算法构造型启发算法插入算法节约算法改进型启发算法Petal算法Sweep算法人工智能算法遗传算法GA蚁群优化算法表1启发式算法分类四、智能算法在物流配送车辆路径问题中的应用（1）混合遗传算法1)量子遗传算法2)遗传算法与模拟退火算法结合（2）混合粒子群算法1)量子粒子群混合算法2)粒子群算法与模拟退火算法（3）混和蚁群算法1）量子蚁群算法2）蚁群算法与粒子群算法结合【课后小结】车辆调度问题车辆调度的优化目标车辆调度问题是在满足一定约束条件下，选择某种目标作为优化目标，实现总配送成本最优。配送车辆优化调度的模型1.有载重约束的车辆调度模型2