几种典型的车辆优化调度问题的模型的分析与建立2

项目一人工智能算法在配送环节应用《物流人工智能技术》任务七几种典型的车辆优化调度问题的模型的分析与建立2目录/CONTENTS01单源点单车型非满载车辆优化调度问题模型02单源点单车型满载和非满载混合车辆优化调度问题模型03有时间窗的非满载车辆优化调度问题模型4【知识目标】1.掌握几种典型的车辆优化调度问题的模型的分析与建立【情感目标】1.具有工匠精神、服务意识、环保意识、质量意识、安全意识；2.培养独立获取信息和自学能力；3.坚定拥护中国共产党领导和我国社会主义制度。【教学目标】1.单源点单车型非满载车辆优化调度问题模型单源点单车型非满载车辆优化调度问题可描述为：有一车场，拥有容量为q的车辆，现有n项货物运输任务，以1，...，n表示，已知任务点i的位置坐标和货运量为gi（i=1，...，n），且0<gi≤q，求满足货运要求的总费用最小或总运距最短的车辆行驶路线。车场可以是泛指车辆发出地，也可以是车库、货场、仓库或配送中心等。1.单源点单车型非满载车辆优化调度问题模型要求每个任务点的货运量必须满足要求，且只能由一辆车装（卸）货，每条配送路径上各任务点的货运量之和不超过车载重量。1.单源点单车型非满载车辆优化调度问题模型为了使路线安排具有一定的弹性，可预先估计一个完成任务所需要的车辆m。如式1所示。其中，[]表示不大于括号内数字的最大整数，0<λ<1，是对装车（或卸车）的复杂程度及约束多少的估计，一般来讲，装（卸）车越复杂，约束越多，λ越小，表示一辆车容纳的货物越少。1.单源点单车型非满载车辆优化调度问题模型首先定义变量，如图所示：那么容量约束的车辆优化调度模型如下：1.单源点单车型非满载车辆优化调度问题模型模型最小化总费用的目标函数中，cij，表示从点i到点j的费用，根据具体实际情况确定，可同时考虑车辆数和运行费用。式（4）、（5）中，C1为相对于运行时间的费用系数：tij为任务点之间的运行时间；c0为车辆的固定费用。减少c0的值会使车辆数增多，而线路长度缩短。若令c1=0，c0>0则模型目标是使用的车辆数最小。当i为任务点时，只有运行费用:式（2.4）式（2.5）当i为车场时，包括固定费用和运行费用如式4所示：2.单源点单车型满载和非满载混合车辆优化调度问题模型单源点单车型满载和非满载混合CVRP问题描述为：有一车场拥有容量为q的车辆，现有n项货物运输任务，以1，…，n表示，已知任务点i的位置坐标和货运量为Gi（i=1，…，n），且Gi≥q，求满足货运要求的总费用最小或总运距最短的车辆行驶路线。2.单源点单车型满载和非满载混合车辆优化调度问题模型对于Gi≥q的任务点i，完成货物运输任务的满载车数为，设为数值不大于的最大整数。一部分是计算Gi≥q的任务点i所需的整车数，进行车辆运输配送，不需要优化策略；另一部分是剩下的不足车辆满载的货物可以与其它货物一同进行非满载配送，可利用之前讲述的非满载车辆优化调度模型进行配送。3.有时间窗的非满载车辆优化调度问题模型有时间窗的非满载车辆优化调度问题可以描述为：有一车场，拥有容量为q的车辆，现有n项货物运输任务，以1，…，n表示，已知任务点i的位置坐标和货运量gi（i=1，…，n），且0＜gi≤q，以及完成点i任务需要的时间表示为fi，且任务i必须在时间窗口[ETi，LTi]开始执行，其中ETi为任务i允许的最早开始时间，LTi为任务i允许的最迟开始时间。如果车到达点i的时间早于ETi，则车辆需要在i处等待；如果车辆到达时间晚于LTi，则任务i将被延迟进行。车场的时间窗范围较大，基本可以不作约束。求满足货运要求的总费用最小或运距最短的车辆行驶路线。3.有时间窗的非满载车辆优化调度问题模型根据时间约束的严格与否，有时间窗的车辆优化调度问题可分为以下两类。硬时间窗VRP是指每项任务必须在要求的时间范围内完成，时间不在这个时间范围，则得到的解为不可行解。软时间窗VRP是指如果某项任务不能在要求的时间范围内完成，则给予一定的惩罚。3.有时间窗的非满载车辆优化调度问题模型在前面的CVP的基础上，考虑时间窗约束，建立有时间窗的车辆优化调度模型。定义变量如下：3.有时间窗的非满载车辆优化调度问题模型1）一般有时间窗的车辆优化调度问题模型式中tij表示车辆从点i到点j的行驶时间。cij表示从点i到点j的费用，根据具体实际情况确定。P1，表示在ETi之前到达任务点i等待的单位时间成本，P2表示在LTi之后到达任务点i的单位时间所得的罚金成本；若车辆在ETi之前到达点i，则增加机会成本P1*（ETi－ti），若车辆在LTi之后到达点i，则增加罚金成本P2*（ti－ETi）车辆到达任务点后的服务开始时间如式6：式（2.6）3.有时间窗的非满载车辆优化调度问题模型要求每个任务点的货运量必须满足要求，且只能由一辆车装（卸）货，每条配送路径上各任务点的货运量之和不超过车载重量。则有时间窗的车辆优化调度模型如式7，8所示：当P1=P2→∞时，以上模型为硬时间窗VRP问题。3.有时间窗的非满载车辆优化调度问题模型传统的基于顾客满意度车辆优化调度模型对于运输服务的时间约束用时间窗表示。其中ETi，为任务i允许的最早开始时间，LTi为任务i允许的最晚开始时间，而[ETi，LTi]表示任务i在该时间范围内开始，顾客满意度最大值为1，否则顾客满意度为0，并且设定惩罚函数进行调节，如图所示。2）基于顾客满意度的有时间窗的车辆优化调度问题模型3.有时间窗的非满载车辆优化调度问题模型然而，顾客满意度和惩罚函数在时间窗范围内不应保持一个恒定值，鉴于此，将每个时间窗分为三种情况和一个特殊点进行考虑，引入一个约定时间（或是一个期望服务的时间），如图所示。3.有时间窗的非满载车辆优化调度问题模型①如果到达时间不超过约定时间，车辆会等待，但是顾客满意度为最大值。同时设定个惩罚函数M1（ti），惩罚值是以单位时间减少的，直到惩罚值的极值为0。②如果到达时间在约定时间和顾客最大的容忍时间之间，顾客一定会等待，设定顾客满意度函数为R（ti），是随着单位时间下降的，同时惩罚函数M2（ti）是随着单位时间增加的。3.有时间窗的非满载车辆优化调度问题模型③如果到达时间超过顾客最大的容忍时间，这种情况不允许发生（可以考虑加入惩罚因子P，P→∞）。④如果到达时间即是约定时间，顾客满意度为1，不需要惩罚。3.有时间窗的非满载车辆优化调度问题模型给定一个时间窗：（0，Ti）U{Ti}U（Ti，LTi）其约束条件如式8所示。则基于顾客满意度的车辆优化调度模型如式9所示：