Hola. Por favor dígame.... La mejor ruta de entrega... Me encantaría ver tu trabajo. Espero saber de usted. 879061916@163.com
Resumen
Este artículo analiza un problema en el que un repartidor necesita entregar mercancías a tiempo lo más rápido posible. Este problema puede considerarse como el problema de Freightliner. Una categoría.
En el primer problema, utilizamos el modelo de inserción del punto más cercano para obtener 30 planes de transporte de carga y tiempos de ruta, y aplicamos el método exhaustivo de permutación completa local para optimizar las rutas obtenidas anteriormente, y se obtuvo la ruta final. : O->18->13->19->24->31->27->27->39->27->31->31->34->40->45->45- > 45->42
->49->42->43->43->38->36->38->35->32->32->32->23-> 23 ->16->14->17->21->26->O, el tiempo total (incluido el tiempo de entrega) es: 228,18 minutos.
En la segunda pregunta, de acuerdo con el principio de prioridad temporal, todos los puntos de entrega de carga se agrupan en bloques, es decir, se priorizan las mercancías con requisitos de tiempo ajustados y se utiliza el método exhaustivo para enumerar la carga. puntos de entrega en cada Ordenar arbitrariamente los bloques, encontrar la ruta más corta entre ellos es el resultado requerido. La ruta final es: O->18->13->19->.24->31->27-> 27->. 39->27->31->31->34->40->45->45->45->42
->49->42->43->43 -& gt ;38->36->38->35->32->32->32->23->23->16->14->17->21->26->O, consumo total Horas (incluyendo tiempo de entrega): 228,18 minutos.
En la tercera pregunta, debido al peso y volumen de la mercancía, el repartidor necesita recoger la mercancía a mitad de camino. Utilizamos las opciones de primera entrega en el punto más lejano y primera entrega en el punto más cercano para dividir las rutas. Según la comparación de los resultados finales, concluimos que la primera opción es mejor, por lo que elegimos la primera opción de entrega.
La ruta final es:
Primer viaje: 0->18->13->11->12->15->25->29->22->20->22->30- >28->33->28->30
->22->15->5->2->4->3->8->1->6->1-> 7->10->9->14->18->0,
Segundo viaje:0->26->31->19->24->31->34-> 40->47->40->37->41->46->48->44->50
->45->36->27->39->. 31->26->0
Tercer viaje:0->21->17->23->16->23->32->35->38->43->42-> 49->42->43->. 38
->36->21->0
El cuarto viaje:0->26->26->26-> 0
El tiempo total es: 394,3 minutos: 394,3 minutos.
Palabras clave: problema de la camilla de mensajería de la empresa de mensajería Método de inserción del vecino cercano Método de alineación completa Método exhaustivo
1 Replanteo del problema
En la industria de la logística, los mensajeros necesitan Entregar los productos con prontitud y rapidez posible y, a menudo, tienen que entregarlos en varios lugares por persona.
Los repartidores de una empresa de entrega urgente existente deben seguir el camino de la Figura 1 para entregar mercancías a múltiples ubicaciones en una ciudad, por lo que es necesario diseñar un plan de entrega para minimizar el tiempo invertido. Suponga que el repartidor solo puede caminar a lo largo de las líneas de conexión en la figura y no puede tomar otras rutas. La Tabla 1 brinda la información de cada carga y la Tabla 2 brinda las coordenadas de los 50 puntos de anclaje.
Supongamos que la capacidad de carga máxima del repartidor es de 50 kg y el volumen máximo de carga es de 1 metro cúbico. La velocidad media de un repartidor es de 24 kilómetros por hora. Cada entrega demora 3 minutos, suponiendo que se realicen varias entregas en el mismo lugar, cada una de las cuales demora 3 minutos.
Ahora, el repartidor tiene que entregar 100 artículos en 50 ubicaciones. Por favor complete las siguientes preguntas.
1. Si desea entregar de 1 a 30 piezas de productos a una ubicación designada y enviarlos de regreso. Diseñe la ruta y el método más rápidos. Da el resultado. Requerir etiquetas en las rutas de entrega.
2. Supongamos que el repartidor comienza a entregar la mercancía a las 8:00 am. Si desea entregar la mercancía del 1 al 30 dentro del tiempo especificado, diseñe la ruta y el método más rápidos para completar la entrega. Se requieren rutas de entrega.
3. Si no es necesario considerar el límite de tiempo de entrega de todos los productos (incluidos los primeros 30 productos), ahora los 100 productos deben entregarse en el lugar designado y devolverse. Diseña la ruta más rápida y la forma de terminar. Exigir que se marquen las rutas de entrega y se indiquen los tiempos de entrega para todos los envíos. Debido a restricciones de peso y volumen, el repartidor podrá regresar a mitad del camino para recoger el artículo. No pienses en tu pausa para el almuerzo.
2. Análisis del problema
El problema de un repartidor que entrega mercancías desde el punto O en el almacén de la empresa de mensajería hasta un lugar designado en la ciudad se puede resolver convirtiéndolo en el camino más corto. en teoría de grafos consideramos cada ubicación de entrega en la ciudad como los vértices del gráfico, y el tiempo requerido para la entrega entre cada punto como el peso en el borde, que se construye en función de la conectividad entre cada punto dada en la Tabla 3 en. la pregunta. Gráfico no dirigido.
Para la pregunta 1, el repartidor debe entregar entre 1 y 30 artículos en un lugar designado y devolverlos lo más rápido posible. Por lo tanto, el problema se puede resolver reduciéndolo a un problema de repartidor.
Para la pregunta dos, el repartidor debe entregar la mercancía en el destino de la manera más rápida dentro del tiempo especificado a partir de las 8:00 am. De la pregunta se puede ver que las ubicaciones correspondientes a los productos 1 ~ 30 se pueden dividir en cuatro bloques según el horario, a saber, de 8:00 a 9:00, de 9:00 a 9:30, de 9:30 a 10:15. , 10:15 a 12:00 Cuatro franjas horarias. Luego se agotan los lugares de entrega para cada período de tiempo para obtener la mejor ruta y se evalúan los resultados para cada período de tiempo.
Para la pregunta 3, sin considerar el plazo de entrega, se consideraron los dos factores de volumen y peso, permitiendo al repartidor recoger la mercancía de ida y vuelta, y exigiendo que el repartidor entregue la mercancía en el forma más rápida La mercancía se entrega en el lugar designado y se devuelve. Dado que el peso total de todos los artículos es 148 kg y el volumen total es 2,98 metros cúbicos, y la capacidad de carga máxima del repartidor es 50 kg y el volumen de carga máximo es 1 metro cúbico, el repartidor hará tres viajes para recoger el bienes, por lo que todas las entregas La ubicación se puede dividir en tres bloques. Para bloquear todos los lugares de entrega, se pueden utilizar tres opciones: encontrar el punto más alejado del punto de partida y agregar el siguiente punto más lejano uno por uno hasta alcanzar la capacidad de carga máxima del repartidor, encontrar el punto más cercano al punto de partida; Y agregue los siguientes puntos más cercanos uno por uno hasta alcanzar la capacidad de carga máxima del repartidor; bloquee artificialmente hasta que se alcance la capacidad de carga máxima del repartidor;
3 Supuestos del modelo
(1) El repartidor solo puede tomar la ruta de conexión indicada en la pregunta y no puede tomar otras rutas;
(2) Supuestos El la capacidad máxima de carga del repartidor es de 50 kilogramos y el volumen máximo de la mercancía transportada es de 1 metro cúbico;
(3) Suponga que la velocidad promedio del repartidor es de 24 kilómetros por hora;
(4) Supongamos que el tiempo de entrega de cada artículo es de 3 minutos, que es el volumen máximo del repartidor. La tarifa de entrega de carga es de 3 minutos. Para simplificar, si hay varias mercancías en el mismo lugar, el cálculo de la entrega se basa simplemente en 3 minutos para cada pieza.
(5) La tarifa de entrega es de 3 minutos. el repartidor no está atrapado en el tráfico durante la entrega, es decir, el operador La entrega urgente no se ve afectada por ningún factor externo;
(6) El conductor de la entrega no considera la pausa para el almuerzo durante la entrega;
(7) Suponga que el conductor de entrega llega al lugar de entrega Llega al punto de entrega después de entregar todos los productos en este sitio;
4 Establecimiento y solución del modelo
4.1 Modelo de solución de ruta para cada sitio
Las coordenadas de cada sitio. Los números de punto en el sistema y los números de estación correspondientes a las mercancías se pueden obtener a través de programación informática del No. 1 al No. 30, como se muestra en la Figura 1-1:
Todas las estaciones de entrega en la Figura 1-1 y los primeros 30 números de puntos de entrega
Según las condiciones conocidas en la pregunta, el problema de entrega puede resolverse como un problema de ruta óptima en la teoría de grafos. El sitio de entrega se considera como el vértice en el gráfico, y la ruta entre los sitios de entrega se usa como el borde y la distancia entre los sitios de entrega se usa como el peso del. borde en el gráfico para formar un gráfico, en el cual punto fijo n=50
Por lo tanto, existe un algoritmo para resolver dos problemas cualesquiera en el gráfico El camino más corto de una línea recta entre sitios, sea el matriz de peso en el gráfico be, donde, es la distancia a.
Cuándo;
=
Otros
Los pasos básicos del algoritmo son:
(1) Matriz de peso de entrada.
(2) Calcular , , , donde los elementos en
(3) van a .
4.2 Solución al Problema 1 Establecimiento del Modelo
1. Modelo de inserción del vecino más cercano:
Este problema puede considerarse como una aplicación del problema de la camilla de carga, ya que no existe un algoritmo preciso para el problema de la camilla de carga y la entrega de las primeras 30 piezas**. * Implica una gran cantidad de datos de 22 sitios, por lo que utilizamos el modelo de inserción del vecino más cercano para aproximar la solución. La idea básica es tomar el punto O como punto de partida, incluirlo en el conjunto, calcular las distancias desde los puntos restantes al conjunto por turno, tomar el punto correspondiente al sitio con la distancia más pequeña como siguiente punto a insertar. en el conjunto, y calcule los puntos correspondientes al punto insertado en el conjunto en secuencia. La distancia entre cada elemento, la posición con la distancia más pequeña se utiliza como la posición del punto insertado en el conjunto. Y así sucesivamente hasta haber recorrido todos los sitios.
El método de inserción del vecino más cercano se implementa de la siguiente manera: (Supongamos que es un gráfico no dirigido ponderado, ***n nodos, donde n=22)
(1) Tome el punto O Cuente los puntos iniciales, establezca un conjunto ordenado (el orden de los elementos en el conjunto es el mejor camino) = { }, y establezca un conjunto a partir de los n-1 puntos restantes = { }, calcule la distancia desde cada elemento en el establezca los elementos en el conjunto Distancia, tome la distancia de cada elemento en el conjunto al conjunto y luego insértelo en el conjunto con la distancia mínima. Tome la distancia mínima de cada elemento del conjunto a cada elemento del conjunto como su distancia correspondiente al conjunto, compare la distancia de cada elemento del conjunto al conjunto, tome el elemento con la distancia más pequeña como el elemento a incluir en el conjunto e insértelo en el conjunto Entre cada elemento, se calcula la distancia y el punto de inserción con la distancia más corta se toma como la posición final del elemento en el conjunto para obtener el conjunto ordenado final. Finalmente se obtiene un conjunto ordenado.
(2) Suponga que el conjunto = { }, = { }, encuentre la distancia desde los elementos en el conjunto de elementos al conjunto por turno, es decir, compare el tamaño del conjunto, tome el valor mínimo como la distancia al conjunto; luego encuentre los elementos a su vez. La distancia entre los elementos del conjunto y el conjunto es comparar el tamaño del conjunto y tomar el valor mínimo como la distancia al conjunto y por analogía, Encuentre la distancia del conjunto de elementos al conjunto. La distancia del conjunto de elementos al conjunto. Compare la distancia entre el conjunto de elementos y el conjunto, e inserte el elemento con la distancia más pequeña en el conjunto de elementos. Para facilitar la comprensión, aquí asumimos que este elemento es, y luego calculamos la distancia total de la ruta insertada en el elemento. conjunto, y use el elemento con la distancia más pequeña a Un conjunto se obtiene como punto de inserción.
(3) Por analogía, hasta que todos los puntos se atraviesen una vez, el conjunto obtenido es el mejor camino.
Según el programa, el mejor camino es:
O->21->17->14->16->23->32->35->38- >36 ->38->43->42->49->42->.45->40
->34->31->18->13->19->24- >31 ->27->39->27->31->26->0
Tiempo total: 230,83 minutos.
En segundo lugar, el modelo exhaustivo de permutación total parcial
Los 22 sitios involucrados en las primeras 30 entregas de mercancías *** tienen una gran cantidad de datos, lo que es difícil de implementar directamente usando el método exhaustivo de permutación completa, por lo que solicito dividirlo en varios bloques grandes y usar el método exhaustivo de permutación completa local dentro de cada bloque grande para obtener la ruta óptima local y luego conectar todos los bloques de cada bloque de ruta. un todo fijando el punto de partida. Un todo. (El algoritmo de modelado específico se muestra en la Pregunta 2 a continuación)
La ruta óptima es:
O->18->13->19->24->31->27 - >27->39->27->31->31->34->40-> ;45->45
->45->42->49->42->43 - >43->38->36->38->35->32->32->32->32->23->23->16- >14->17->21->26-> 26 ->O
El tiempo total fue: 228,18 minutos.
Al comparar los resultados de los dos modelos, se puede ver claramente que los resultados obtenidos al utilizar el método exhaustivo después de la segmentación son mejores que los del primero. Por lo tanto, la selección de las primeras 30 rutas de entrega de carga utiliza el. Método exhaustivo de matriz total parcial. Método de elevación:
O->18->13->19->24->31->27->27->39->27->31->31. ->34->40 ->45->45
->45->42->49->42->43->43->38->36->38->35- >.32->32 ->32->23->23->16->14->17->21->26->O
Tiempo total: 228,18 minutos.
La ruta es como se muestra en la figura 1-2:
Figura 1-2 Diagrama de ruta de transporte óptima de los primeros 30 lotes de mercancías
4.3 Modelado de solución del problema 2
Este problema utiliza Con la idea de bloquear, se utiliza el método exhaustivo de permutación local y completa para encontrar la ruta óptima para cada pieza de producto. Debido a las limitaciones de transporte teniendo en cuenta el tiempo de entrega, damos prioridad al tiempo de entrega, es decir, dividimos el tiempo de entrega de todos los productos en bloques y utilizamos el método exhaustivo de permutación completa local para encontrar la ruta dentro de cada bloque y determinar su total. entrega Si el tiempo cumple con el tiempo especificado. Los pasos básicos son:
(1) El primer horario de entrega entre 8:00-9:00 es: 13, 18, 39, 27, 24, 27, sin contar sitios duplicados, total * ***, un total de 5 sitios, el mejor camino obtenido al comparar el tiempo mediante el método exhaustivo es: 18->13->24->27->39, considerando que el tiempo total de entrega es 57,1 minutos.
(2) Los sitios de entrega del segundo período de tiempo entre las 9:00-9:30 son 31, 31, 34, 40, 45, 45, 45, 45, sin contar los sitios duplicados, hay 4 estaciones en total, y el mejor recorrido se obtiene comparando el tiempo mediante el método exhaustivo: 31->34->40->45, considerando que el tiempo de entrega es de 57,1 minutos. >45, teniendo en cuenta el tiempo de entrega el tiempo total es de 46,05 minutos.
(3) En el tercer periodo de tiempo de 9:30 a 10:15, los números entregados al sitio son: 42, 49, 43, 43, 38, excluyendo sitios duplicados, el total es * *** Hay 4 sitios, y el camino subóptimo obtenido después de una comparación exhaustiva es: 42->49->43->43->43->38, con un tiempo total de 46,05 minutos. 43->38, teniendo en cuenta el tiempo de entrega, el tiempo total es de 39,58 minutos.
(4) En el cuarto período de tiempo de 10:15 a 12:00, 36, 32, 23, 16, 14, 17, 21 y 26 se entregan al sitio, sin contar los sitios duplicados. **** Hay 8 sitios y la mejor ruta se obtiene comparando el tiempo utilizando el método exhaustivo: gt;23->16->14->17->21->26 El tiempo total incluida la transmisión. el tiempo es 81,97 minutos.
Por lo tanto, los resultados obtenidos al segmentar según el periodo de tiempo dado en la pregunta se muestran en la Tabla 1:
Tabla de segmentación onsite
Parte
Tiempo
Periodo
Segmento
Número de envío
Lugar de entrega
Peso
Volumen
Tiempo
Mejor ruta
Tiempo (incluyendo entrega
tiempo de envío)/Minutos
1
13
2.5
0.0316
9:00
18
57.1
2
18
0.5
0.0354
9:00
13
13
39
2.56
0.0595
9:00
24
19
27
2.45
0.0545
9:00
27
20
24
2.93
0.052
9:00
27
22
27
2.25
0.0018
9: 00
39
el
segundo
Tiempo
Intervalo
Segmento
3
31
1.18
0.0268
9:30
31
46.05
11
45
1.1
0.0287
9:30
31
14
45
2.28
0.0501
9:30
34
21
31
0.8
0.0108
9:30
40
24
34
2.8
0.0103
9:30
45
25
40
2.14
0.0155
9:30
45
26
45
0,68
0,0682
9:30
45
Par.
La tercera vez
Tiempo
Intervalo
10
38
1.33
0.0319
10:15
42
39,58
12
43
0,95
0,0228
10:15
49
15
42
2,85
0,019
10:15
43
16
43
1.7
0.0782
10:15
43
27
49
1.35
0.0144
10:15
38
Segmento
Cuatro
Tiempo
Intervalo
Segmento<
/p>
4
26
1.56
0.035
12:00
36
85.45
5
21
2.15
0.0377
12:00.00
32
6
14
1.72
0.01
12:00
32
7
17
1.38
0.0109
12:00
32
8
23
1.4
0.0426
12:00
23
9
32
0.7
0.0481
12:00
23
17
32
0.25
0.0512
12:00
16
18
36
1.79
0.0184
12:00
14
23
26
1.57
0.021
12:00
17
28
32
0.52
0.002
12:00
21
29
23
2.91
0.0587
12:00
26
30
16
1.2
0.0429
12:00
26
Según la Tabla 1, la ruta de entrega es la siguiente:
O->18->13->19->24 ->31 ->27->27->39->27->31->31->34->40->45->45
->45->42->49 ->42 ->43->43->38->36->38->35->32->32->32->23->23->16->14->17->21-> 26-> 26->26->31->34->40->45->45
->45->45-> >26->O, tiempo total: 228,18 minutos.
El mapa de ruta de transporte óptimo cuando se consideran limitaciones de tiempo se muestra en la siguiente figura:
Figura 1-3 El mapa de ruta de transporte óptimo para los primeros 30 lotes de mercancías cuando se consideran limitaciones de tiempo
4.4 Modelación del Problema 3
Considerando las restricciones de peso y volumen de la mercancía transportada por el repartidor, ignorando el tiempo límite de entrega ya que el peso total de todos los artículos es de 148 kg. , el volumen total es de 2,98 metros cúbicos, mientras que la capacidad de carga máxima del repartidor es de 50 kg y el volumen máximo es de 1 metro cúbico. El repartidor realizará tres viajes para recoger la mercancía, por lo que se deberán dividir todos los lugares de entrega. en al menos tres bloques.
Usamos dos esquemas de bloqueo para esta pregunta, que son:
(1) Método de prioridad del punto de entrega más lejano:
Encuentre el punto O más alejado del punto de partida y use este punto Buscar los puntos más cercanos alrededor del centro del círculo hasta que alcance la capacidad de carga máxima y la capacidad de carga máxima del repartidor. Entre los puntos restantes, utilice el siguiente punto más alejado del punto O como centro para encontrar los puntos circundantes hasta que el repartidor esté. alcanzada hasta la capacidad máxima de carga y la capacidad máxima de carga de la tripulación de carga. El punto O restante toma el siguiente punto más alejado del punto O como centro del círculo hasta alcanzar la capacidad de carga máxima y el volumen de carga máximo del repartidor, hasta que se entregue toda la mercancía. Según el cálculo de los datos del encabezado, el punto más alejado del punto O son 2 puntos, por lo que los bloques de datos de un conjunto de puntos de entrega centrados en 2 puntos son los siguientes: 2, 3, 4, 5, 8, 15, 15 , 1 ,6,7,7,11,11,12,12,12,13,13,10,10,18,18,20,20,22,25,25,25,25,29,30,28 ,9, 33, 33, 14, 14, ****35 estaciones, el peso total entregado por el repartidor es 48.54 kilogramos, el volumen total es 0.9857 metros cúbicos, sin contar estaciones duplicadas, *** hay 23 estaciones de entrega , Los primeros 12 sitios son parte y los últimos 11 sitios son parte. La ruta óptima obtenida por método exhaustivo es:
18->13->11->12->15->. 25- >29->22->20->22->30->28->33->28->30->22->15->5->2->4->3->.8 -> 1->6->1->7->10->9->14, tiempo total 167,48 minutos. Excluyendo estos 23 sitios, se puede ver en los resultados del cálculo que el punto más alejado del punto O es el punto 48, y los datos de un grupo de puntos de entrega centrados en este punto son 48, 44, 46, 46, 46, 41. 41,50,47,40,40,37,37,34,34,34,19,19,24,24,45,45,45,45,45,31,31,31,27,27,27 , 27, 39, 39, 39, ***31 estaciones, el peso total entregado por el mensajero es de 50 kilogramos, el volumen total es de 0,9573 metros cúbicos, excluyendo estaciones duplicadas, *** hay 15 estaciones de entrega, las primeras 11 estaciones se toman es una parte, y los últimos cuatro sitios son una parte. La ruta óptima se encuentra mediante el método exhaustivo:
19->24->31->34->40->47->40. -> 37->41->46->48->44->50->45->36
>47->40->37->41->46->48-> 44- >50->45->36
->27->39, el tiempo total es de 141,82 minutos. Como parte del mismo, después de las dos primeras estaciones, se calcula la estación más alejada del punto O. Son 17 puntos El dato de un grupo de puntos de entrega centrados en este punto es de 9751 m3 excluyendo paradas repetidas, hay un total de 11 paradas de entrega. El recorrido óptimo se obtiene por método exhaustivo:
17->23->16->23->32->35->38->43->42->49->42->43->38->36->21, entre los cuales el tiempo total es 78,04 minutos.
Finalmente, utilizando 26, 26 y 26 como grupo para devolver datos de puntos, el peso total entregado por el mensajero en 3 estaciones es de 4,39 kilogramos y el volumen total es de 0,0619 metros cúbicos. que no se repiten son 1 sitio con un tiempo total de 6,96 minutos.
La combinación de los datos de estos cuatro bloques da un tiempo total de envío de 394,3 minutos.
(2) El método de prioridad del punto de entrega más cercano:
Primero busque el punto más cercano al punto de partida y luego agregue el siguiente punto más cercano uno por uno hasta la carga máxima. Se alcanza la capacidad del repartidor y la capacidad de carga máxima, y luego buscar el punto más cercano al punto O entre los puntos restantes hasta alcanzar la capacidad de carga máxima y la capacidad de carga máxima del repartidor, hasta que se entregue toda la mercancía. Según los cálculos basados en los datos de la pregunta, el punto más cercano al punto O es el punto 26, por lo que un conjunto de datos del bloque de puntos de entrega con el punto 26 como centro inicial son: 26, 26, 26, 18, 18, 21 , 21, 23, 23, 23, 23, 23, 23, 27, 27, 27, 27, 27, 27, 31, 31, 31, 31, 34, 34, 34, 34, 36, 36, 36, 36 , Estaciones 36, 39, 39, 24, 24, 24, 17, 17, 17, 17, 17, 17, 11, ***31, el peso total entregado por el mensajero es 45,77 kilogramos y el volumen total es 0,936 metros cúbicos, sin contar Sólo se repiten 11 estaciones, y el recorrido óptimo obtenido por método exhaustivo es:
26->21->17->23->36->27->39 ->31 ->34- >24->18, tiempo total 81,12 minutos. Entre estos 11 sitios, el punto más cercano al punto O se calcula como 25 de los puntos restantes, y este punto es el bloque de datos de un conjunto de puntos de entrega que comienzan desde el centro: 25, 25, 25, 37, 37, 42. 42,43,43,43,43,50,1,47,3,6,15,15,29,22,30,49,49,41,41,28,20,20,44,4,4 , 4, 4, 4, 20, hay un total de 33 puntos. El peso total entregado por el mensajero es 44,55 kilogramos y el volumen total es 0,8004 metros cúbicos. Solo hay 20 puntos sin puntos repetidos. parte de él, y los últimos 8 puntos son una parte, y el camino óptimo obtenido por método exhaustivo es:
25->29->22->30->33->28->20 ->15->4->3->1->6->47->37->41->44->
50->49->42->43, el tiempo total es 219,5 puntos. Además de estos 31 puntos, mediante cálculo, el punto más cercano al punto O entre los puntos restantes son 38 puntos. Un conjunto de datos de bloque a partir de este punto es el siguiente: 32, 32, 32, 32, 32, 32, 32. , 32, 32, 32, 32, 35, 40, 40, 45, 45, 45, 45, 45, 45, 45, 45, 45, 8, 10, 10, 7, 7, 15, el total es 35 puntos , el peso total entregado por el repartidor es de 48,73 kilogramos y el volumen total es de 0,9839 metros cúbicos. Solo hay 15 estaciones que no se repiten. Las primeras 10 estaciones son parte del mismo. Utilice el método exhaustivo para encontrar la ruta óptima:
19->13->11->12->8->7->10->9->14->16->32 ->35->38- >45->40, el tiempo total es: 125,35 Entre los puntos restantes, el punto 2 es el más cercano al punto O en términos de cantidad calculada. Tomando este punto como punto de partida, un conjunto de bloques de datos son 2, 5, 48, 46, 46, 46, 46, 46, **** 6 estaciones. El peso total transportado por el mensajero es de 8,95 kilogramos y el total. el volumen es de 0.2597 metros cúbicos.m, solo hay 4 sitios sin contar duplicados. El camino óptimo obtenido mediante el método exhaustivo es:
2->5->48->46, el tiempo total: 125,55 minutos.
Combinando los datos de estos cuatro bloques, el tiempo total es: 551,52 minutos.
Resumen: A través del cálculo, se puede ver que el tiempo total de entrega obtenido por la aplicación uno es 394,3 minutos; el tiempo total de entrega obtenido por el plan de aplicación dos es 551,52 minutos. El plan uno es mejor que el plan dos. Por lo tanto, considerando las mercancías según el peso y el volumen, la ruta óptima para completar 100 tareas de entrega es:
El primer viaje: 0->18->13->46, el tiempo total es : 125,55 minutos. gt;13->11->12->15->25->29->22->20->22->30->28->33->28->30
- >22->15->5->2- >4->3->8->1->6->1->7->10->9->14->18->0,
El segundo viaje:0->26->31->19->24->31->34- >40->47->40->37->41->46->48- >44
->50->45->36->27->39->27->31->26->0
Tercer viaje:0->21 ->17->23->16->23->32->35->38->43->42->49->42->43->38
->36- >21->. 0
El cuarto viaje:0->26->26->26->0
Tiempo total: 394,3 minutos.
5 Evaluación del modelo
5.1 Evaluación del modelo 1
Primero use el método de inserción del vecino más cercano para obtener su ruta óptima aproximada y luego use el método exhaustivo para obtener el bloque por bloques La mejor ruta, el método exhaustivo de permutación parcial y total, tiene un rango de aplicación más amplio, lo que debería deberse a que no está limitado por la cantidad de datos.
5.2 Evaluación del Modelo 2
En la primera pregunta, podemos agregar tiempo como condición de restricción. Podemos dividir las primeras 30 piezas según el tiempo de entrega dado en la pregunta. La ubicación de entrega de los productos se divide en cuatro partes, lo que reduce la cantidad de datos, por lo que podemos utilizar el método exhaustivo para representar con precisión la ruta de entrega de cada período de tiempo y luego basarnos en los sitios al principio y al final de cada período de tiempo, Obtenga la ruta óptima final. El camino óptimo final.
5.3 Evaluación del Modelo 3
De acuerdo con las restricciones del volumen máximo de entrega conocido en la pregunta y el volumen máximo de entrega del repartidor, toda la mercancía debe dividirse en al menos tres grupos, ida y vuelta Entregado tres veces hasta la ubicación final. Diferentes esquemas de agrupación conducen a resultados diferentes. En esta pregunta, utilizamos dos esquemas, a saber, el método de prioridad del punto más lejano y el método de prioridad del punto más cercano, para calcular los resultados. Esto puede hacer que los resultados sean más convincentes. Sin embargo, el método de clasificación solo selecciona dos esquemas de clasificación típicos, lo cual no es lo suficientemente completo. Puede haber mejores esquemas y esperamos su discusión.