Excelentes artículos sobre modelado matemático

: si se elige caminar; para la enésima ruta del metro de la k-ésima ruta, es una variable 0-1, que indica no elegir caminar, indica elegir caminar

Tres supuestos modelo

3.1 Supuestos básicos

1. El tiempo medio de viaje de las estaciones de autobús adyacentes (incluido el tiempo de parada): 3 minutos

2. El tiempo medio de viaje a las estaciones de metro adyacentes (incluido el tiempo de parada): 2,5 minutos

3. El tiempo promedio de traslado en autobús: 5 minutos (incluidos 2 minutos de caminata)

4. El tiempo promedio que se tarda en trasladarse del metro al metro: 4 minutos (incluidos 2 minutos). de tiempo caminando)

5. El tiempo promedio que se tarda en trasladarse del metro al autobús: 7 minutos (de los cuales se necesitan 4 minutos caminando)

6. tiempo necesario para el traslado del autobús al metro: 6 minutos (incluidos 4 minutos de caminata)

7. Tarifa de autobús: dividida en tarifa única y tarifa segmentada

Tarifa única: 1. yuanes

La tarifa segmentada es: 0~20 estaciones: 1 yuan

21~40 estaciones: 2 yuanes

Más de 40 estaciones: 3 yuanes

8. Tarifa de metro: 3 yuanes (independientemente del traslado entre líneas de metro)

9. Suponiendo que esté en la misma estación de metro, puede realizar transbordo entre dos estaciones de autobús correspondientes a través de la estación de metro sin pagar el metro. tarifas

3.2 Otros supuestos

10. El número de veces que el solicitante se traslada a los autobuses no supera el doble;

11. camino;

12. La línea de metro T2 también es circular de doble sentido;

13 Todos los autobuses funcionan con normalidad y no habrá atascos;

14. Todos los autobuses y trenes paran en la estación

Análisis de cuatro problemas

Durante los Juegos Olímpicos de Beijing, cómo el público elige la ruta óptima de autobús o de transbordo entre las Muchas rutas de transporte para ir a los Juegos Olímpicos. Éste es el problema central que queremos resolver. Para abordar este problema, consideramos encontrar la ruta óptima desde la perspectiva de las rutas de autobús. Primero, busque todas las rutas que pasan por dos sitios cualesquiera (lugares públicos y sedes olímpicas) y guárdelas para formar un archivo de datos.

Estas rutas pueden incluir líneas de autobús directas, o pueden estar formadas por la intersección de dos líneas de autobús (en este caso, es necesario hacer transbordo a un autobús una vez), o incluso la intersección de más líneas de autobús. Luego busque la ruta óptima entre estas rutas factibles.

Para la evaluación de rutas, podemos usar el tiempo total de viaje, el número total de transferencias y el costo total como indicadores respectivamente, o podemos estandarizar los tres indicadores y asignar diferentes pesos para formar un indicador integral. La ruta óptima debe ser aquella que tenga el menor tiempo total de viaje, el menor costo total, el menor número total de transbordos o las tres. La razón por la que consideramos los objetivos de esta manera es porque los objetivos que persiguen los investigadores de diferentes edades serán diferentes. Por ejemplo, los jóvenes están más interesados ​​en las competiciones, por lo que optarán por llegar a las sedes olímpicas en el menor tiempo posible. para ver los juegos. Las personas de mediana edad pueden estar más inclinadas a tener el índice integral más pequeño, es decir, transferencias más rápidas, más económicas y menos frecuentes. Las personas mayores siempre quieren ver los Juegos Olímpicos de la forma más económica. Para las personas con discapacidad, es mejor minimizar el número total de transferencias.

Los diferentes requisitos de consulta de ruta se representan a continuación en la Figura 4.1:

Figura 4.1 Mapa de destino de la consulta de ruta de autobús

Después del análisis, la solución a este problema se reduce a un requisito El problema de la ruta más corta, pero el algoritmo tradicional de la ruta más corta de Dijkstra no es adecuado para este problema, porque la estructura de almacenamiento y el método de cálculo utilizados por el algoritmo de Dijkstra son difíciles de hacer frente a la complejidad de la topología de la red de la línea de autobús, y debido a Problemas de eficiencia de ejecución, es difícil de satisfacer. Los sistemas en tiempo real tienen requisitos de tiempo estrictos.

Por esta razón, adoptamos un algoritmo de amplitud primero eficiente y eficiente en el proceso de solución real. La idea básica es buscar un punto específico cada vez y agregar todos sus puntos vecinos no visitados a la cola de búsqueda. El proceso de búsqueda se repite hasta que la cola está vacía. Este método se explica en detalle más adelante.

5 Preparación antes del modelado

Para facilitar el modelado y la programación posteriores, es necesario que realicemos un trabajo preparatorio antes de establecer este modelo.

5.1 Almacenamiento de datos

Dado que el formato de datos dado no está muy estandarizado, debemos procesarlo en el formato de almacenamiento de datos que necesitamos. Lea la información de la estación en la línea del archivo proporcionado y guárdela en un documento de texto. El formato de almacenamiento es: dos líneas de datos La primera línea representa la información de la estación en la línea de enlace ascendente y la segunda línea representa la información de la estación en. la línea de enlace descendente Entre ellos La etiqueta de ruta descendente debe agregarse con 520 sobre la base de la etiqueta original para distinguir la línea ascendente y la línea descendente.

Si los nombres de las estaciones de la línea de enlace ascendente y de la línea de enlace descendente no son exactamente iguales, entonces las dos filas de datos almacenados no son exactamente iguales. Tome la línea de autobús L009 como ejemplo:

L009: 3739 0359 1477 2159 2377 2211 2482 2480 3439 1920 1921 0180 2020 3027 2981

L529：2981 3027 2020 0180 1921 1920 3439 3440 2482 22 11 2377 2159 1478 0359 3739

L529 corresponde al enlace descendente L009.

Si la línea de enlace descendente devuelve la misma ruta que la línea de enlace ascendente, entonces el orden de la información de la estación en las dos líneas de datos almacenados simplemente se invierte. Tome la línea de autobús L001 como ejemplo:

L001: 0619 1914 0388 0348 0392 0429 0436 3885 3612 0819 3524 0820 3914 0128 0710

L521:0710 0128 3914 0820 3524 0819 3612 3885 0436 0429 03 92 0348 0388 1914 0619

Si es una línea circular (como se muestra en la Figura 5.1), puede ser equivalente a dos líneas:

En el sentido de las agujas del reloj: S1→S2→S3→S4→S1→S2→S3→S4 ;

Dirección inversa a las agujas del reloj: S1→S4→S3→S2→S1→S4→S3→S2.

Tras el análisis, las funciones de estas dos "rutas de sentido único" son equivalentes a las rutas circulares originales

Figura 5.1 Diagrama esquemático de rutas circulares

Tomar línea circular de autobús L158 como Por ejemplo, los datos almacenados en esta ruta circular son los siguientes:

L153: 534 649 2355 1212 812 171 170 811 2600 172 1585 814 264 3513 1215 1217 251 2604 2606 534 649 2355 121 2 812 171 170 811 2600 172 1585 814 264 3513 1215 1217 251 2604 2606

L673: 534 2606 2604 251 1217 1215 3513 81 4 1585 172 2600 811 170 171 812 1212 2355 6 49 534 2606 2604 251 1217 1215 3513 264 814 1585 172 2600 811 170 171 812 1212 2355 649

Aquí, la L153 se considera la ruta ascendente y la L673 la ruta descendente. De esta manera, se pueden obtener dos líneas de información de almacenamiento de líneas para cada línea de autobús.

5.2 Buscar rutas de autobús que pasan por cada sitio

Procese la información obtenida en 5.1, encuentre todas las rutas de autobús que pasan por cada sitio y guárdelas en el archivo de datos.

Por ejemplo, a través de la búsqueda, las líneas que pasan por el sitio S0001 y las líneas que pasan por el sitio S0002 son las siguientes:

Las líneas que pasan por S0001 son: L421

Las líneas que pasan por S0002 Las líneas son: L027 L152 L365 L395 L485

5.3 Cuente las paradas que se cruzan (similares) de dos líneas de autobús cualesquiera

Cuente las paradas que se cruzan (similares) de dos líneas de autobús cualesquiera a su vez), guárdelo en una matriz A de 1040 × 1040, pero los elementos de esta matriz son vectores con dimensiones inciertas. Durante la implementación específica, se pueden representar mediante colas.

Por ejemplo: La parada donde la línea de autobús L001 se cruza con la línea de autobús L025 es A[1][25]={S0619, S1914, S0388, S0348}.

Establecimiento y solución de los seis modelos

6.1 Establecimiento del modelo uno

Este modelo está dirigido al problema uno, considerando únicamente las rutas de autobús, averiguando primero el procese dos paradas y rutas de autobús cualesquiera con hasta dos transferencias de autobús, y luego busque la ruta óptima según las necesidades de los diferentes interesados.

6.1.1 Representación matemática de rutas de autobús

Existen muchas situaciones para la ruta entre dos estaciones cualesquiera. Si se permiten un máximo de dos transbordos, las rutas de transbordo serán las correspondientes. las cuatro situaciones de la Figura 6.1.

A y B en la figura son las estaciones de salida y terminal, y C, D, E y F son estaciones de transferencia.

Figura 6.1 Mapa de ruta de autobús

Para dos estaciones de autobús cualesquiera, las líneas de autobús que pasan se expresan como, sí; las líneas de autobús que pasan se expresan como, sí;

1) Una ruta directa (que se muestra en la Figura 6.1(a)) se expresa como:

2) Una ruta con una transferencia (que se muestra en la Figura 6.1(b)) se expresa como:

Donde: SC es una intersección de , ;

3) La ruta de dos transferencias (como se muestra en la Figura 6.1(c)) se expresa como:

A través En el proceso de modelado de rutas de transferencia anterior, se puede ver que se puede establecer una relación iterativa entre diferentes tiempos de transferencia, y luego se pueden encontrar rutas con más tiempos de transferencia. Sin embargo, considerando la situación real, es mejor realizar transferencias no más de 2 veces, por lo que este artículo no analiza la situación de tres o más transferencias.

6.1.2 Establecimiento del modelo de ruta óptimo

Una vez que se encuentran las rutas factibles entre dos estaciones de autobuses, estas rutas se pueden seleccionar de acuerdo con las diferentes necesidades. encontrado:

1) El modelo que toma el menor tiempo como ruta óptima: el tiempo de viaje es igual a la suma del tiempo de viaje y el tiempo de traslado.

(Fórmula 6.1)

Entre ellas, la k-ésima ruta es una o más de las rutas de transferencia anteriores.

2) Un modelo que toma el menor número de transbordos como ruta óptima:

(Fórmula 6.2)

Este modelo equivale a la ruta de transbordo directo para lo anterior, considere la prioridad de una o dos transferencias.

3) El modelo que toma el menor coste como ruta óptima:

(Fórmula 6.3)

Entre ellos, (Fórmula 6.4)

6.1.3 Descripción del algoritmo del modelo

Para el modelo de optimización de este problema, utilizamos el algoritmo de amplitud primero para encontrar la ruta factible entre dos sitios cualesquiera y luego buscamos la ruta óptima. . Ahora aplique este algoritmo a este problema y descríbalo de la siguiente manera con referencia a la Figura 6.2: (En esta figura, , , , representan estaciones de autobuses, , , , , representan rutas de autobuses. Entre ellas (a), (b) , (c) La figura muestra la situación del viaje directo de un punto a otro, un transbordo y dos transbordos respectivamente)

Figura 6.2 Mapa de autobuses directos y transbordos

(1) Primero enter Las dos estaciones que deben consultarse son (se supone que es la estación de inicio y es la estación terminal);

(2) Busque las líneas de autobús que pasan (i=1, 2,... ,m) y las rutas de Autobús que pasan (=1, 2, ..., n) se almacenan en el archivo de datos para determinar si existe la misma ruta y si hay una ruta directa entre la estación y la ruta con la menor cantidad; número de viajes (el número de transbordos es igual a 0 si hay varias rutas directas, la ruta con el menor tiempo se puede encontrar de esta manera, todas las rutas directas se pueden encontrar y almacenar en el archivo de datos; p >

(3) Encuentre otra parada en la línea de autobús que pasa (como en la Figura 6.2) y otra parada en la línea de autobús que pasa.

Determine si existe el mismo punto en y Si existe (como en la Figura 6.2), hay una ruta de transferencia entre la estación y (como en la Figura 6.2), y el mismo punto es la estación de transferencia de esta manera; puede averiguar Se obtiene una ruta de transferencia y se almacena en el archivo de datos;

(4) Luego busque autobuses que pasen por otra parada (como en la Figura 6.2) en la línea que no sea la estación (como en Figura 6.2) Línea (como en la Figura 6.2), busque otras estaciones en la línea de autobús, juzgue, si hay los mismos puntos que otras estaciones en la línea de autobús que pasan (como en la Figura 6.2), entonces hay una cuadrática entre La ruta de transferencia (, , ) en la Figura 6.2, el mismo punto y el punto es la estación de transferencia; almacene esta ruta de transferencia secundaria en el archivo de datos

(5) Para lo anterior, las diferentes rutas almacenadas pasan por el; Se buscan dos sitios para encontrar rutas óptimas basadas en diferentes modelos y se obtiene la ruta óptima que satisface al solicitante.

6. 1. 4 Solución al Modelo 1

De acuerdo con el algoritmo anterior y el modelo 1 establecido previamente, programando con VC (ver anexo del programa) se pueden obtener los resultados. bajo diferentes objetivos.

1) La ruta óptima con el menor consumo de tiempo como objetivo

El tiempo desde la estación inicial S3359 hasta la estación final S1828 es de al menos 64 minutos. La ruta óptima con el. consume menos tiempo (Hay 28 rutas (con menos transbordos y rutas menos costosas) (Nota: la Tabla 6.1 selecciona 10 de ellas para su representación);

El tiempo desde la estación inicial S1557 hasta la estación final S0481 es al menos 106 min, hay 2 rutas óptimas que toman el menor tiempo; desde la estación de partida S0971 hasta el destino final S0485 toma al menos 106 min, hay 2 rutas óptimas que toman el menor tiempo desde la estación de partida S0008 hasta el destino final S0073; al menos 106 minutos Se necesitan al menos 67 minutos, y hay 2 rutas óptimas que toman el menor tiempo; desde la estación inicial S0148 hasta la estación final S0485 toma al menos 106 minutos, y hay 3 rutas óptimas que toman el menor tiempo; desde la estación inicial S0087 hasta la estación final. Se necesitan al menos 46 minutos para llegar a la estación S3676, y hay 12 rutas óptimas que toman el menor tiempo. Las rutas óptimas que toman el menor tiempo se muestran en la Tabla 6.1.

S3359 L0535 S2903 L1005 S1784 L0687 S1828 2 3

S3359 L0535 S2903 L1005 S1784 L0737 S1828 2 3

S3359 L0123 S2903 L1005 S1784 L0 87 S1828 2 3

S3359 L0123 S2903 L1005 S1784 L0737 S1828 2 3

S3359 L0652 S2903 L1005 S1784 L0687 S1828 2 3

S3359 L0652 S2903 L1005 S1784 7 S1828 2 3

S3359 L0844 S2027 L1005 S1784 L0687 S1828 2 3

S3359 L0844 S2027 L1005 S1784 L0737 S1828 2 3

S3359 L0844 S1746 L1005 S1784 L0687 S 1828 2 3 >

S3359 L0844 S1746 L1005 S1784 L0737 S1828 2 3

S1557 L0604 S1919 L0709 S3186 L0980 S0481 2 3

S1557 L0883 S1919 L0709 S3186 L0980 S 04 81 2 3

S0971 L0533 S2517 L0810 S2480 L0937 S0485 2 3

S0971 L0533 S2517 L0296 S2480 L0937 S0485 2 3

S0008 L0198 S3766 L0296 S2184 L0345 073 2 3

S0008 L0198 S3766 L0296 S2184 L0345 S0073 2 3

S0148 L0308 S0036 L0156 S2210 L0937 S0485 2 3

S0148 L0308 S0036 L0156 S3332 L0937 5 2 3

S0148 L03 08 S0036 L0156 S3351 L0937 S0485 2 3

S0087 L0541 S0088 L0231 S0427 L0097 S3676 2 3

S0087 L0541 S0088 L0231 S0427 L0982 S3676 2

S0087 L0541 S0088 L09 01 S0427 L0097 S3676 2 3

S0087 L0541 S0088 L0901 S0427 L0982 S3676 2 3

S0087 L0206 S0088 L0231 S0427 L0097 S3676 2

S0087 L0206 S0088 L0231 S0427 L0982 S3676 2 3

S0087 L0206 S0088 L0901

S0427 L0097 S3676 2 3

S0087 L0206 S0088 L0901 S0427 L0982 S3676 2 3

S0087 L0974 S0088 L0231 S0427 L0097 S3676 2 3

S0087 L09 S0088 L0231 S0427 L0982 S3676 2 3

S0087 L0974 S0088 L0901 S0427 L0097 S3676 2 3

S0087 L0974 S0088 L0901 S0427 L0982 S3676 2 3

2) El número mínimo de transferencias es La ruta óptima hacia el objetivo

El número mínimo de transbordos desde la estación inicial S3359 hasta la estación final S1828 es 1, y la ruta óptima con el menor número de transbordos (la ruta que lleva menos tiempo y ahorra costos) Hay 2;

El número mínimo de transferencias desde la estación inicial S1557 a la estación final S0481 es 2, y hay 2 rutas óptimas con la menor cantidad de transferencias, que son las mismas que las óptimas ruta que consume menos tiempo (indicada en la Tabla 6.1, la misma a continuación);

El número mínimo de transferencias desde la estación inicial S0971 a la estación final S0485 es 1, y hay 1 ruta óptima con la menor número de transbordos;

p>

El número mínimo de transbordos desde la estación inicial S0008 a la estación final S0073 es 1, y hay 9 rutas óptimas con el menor número de transbordos;

Desde la estación inicial S0148 hasta la estación final S0148 El número mínimo de transbordos para S0485 es 2, y las tres rutas óptimas con el menor número de transbordos son las mismas que la ruta óptima que lleva menos tiempo;

El número mínimo de traslados desde la estación de inicio S0087 hasta el destino final S3676. El número de viajes es 2, y 6 de las rutas óptimas con menos traslados son las mismas que la ruta óptima con el menor consumo de tiempo;

Las rutas óptimas restantes con la menor cantidad de transferencias se muestran en la Tabla 6.2.

Tabla 6.2 Tabla de ruta óptima con el menor número de transbordos

Línea de autobús de la estación de inicio, línea de autobús de la estación de transbordo, tiempo y coste de la estación final

S3359 L0956 S1784 L0687 S1828 101 3

S3359 L0956 S1784 L0737 S1828 101 3

S0971 L0533 S2184 L0937 S0485 128 3

S0008 L0679 S 0291 L0578 S0073 83 2

S0008 L0679 S0491 L0578 S0073 83 2

S0008 L0679 S2559 L0578 S0073 83 2

S0008 L0679 S2683 L0578 S0073 83 2

S0008 L0679 4 L0578 S0073 83 2

S0008 L0875 S2263 L0345 S0073 83 2

S0008 L0875 S2303 L0345 S0073 83 2

S0008 L0875 S3917 L0345 S0073 83 2

S0008 L0983 S2083 L0057 S0073 83 2

3) La ruta óptima con el menor coste como meta

El coste mínimo desde la estación inicial S3359 hasta la estación final S1828 es 3 yuanes, hay 30 rutas óptimas con el menor costo (ruta que toma menos tiempo y menos transbordos), de las cuales 28 rutas toman 64 minutos y tienen 2 transbordos, y las otras dos rutas El tiempo requerido es de 101 minutos, y el número de los traslados son 1;

El costo mínimo desde la estación inicial S1557 hasta la estación final S0481 es 3 yuanes. Hay 2 rutas óptimas con el menor costo. El tiempo requerido es de 106 minutos y el número de traslados. es 2;

El costo mínimo desde la estación inicial S0971 hasta la estación final S0485 es 3 yuanes. Hay 3 rutas óptimas con el menor costo, dos de las cuales requieren tiempo. El tiempo requerido para la otra ruta es. 106 minutos, y el número de transbordos es 2 veces El tiempo requerido para la otra ruta es 128 minutos, y el número de transbordos es 1 vez;

La tarifa mínima desde la estación inicial S0008 hasta la final. la estación S0073 cuesta 2 yuanes. Hay 9 rutas óptimas con el menor costo, el tiempo requerido es 83 minutos y el número de transbordos es 1;

El costo mínimo desde la estación de inicio S0148 hasta el destino final. S0485 cuesta 3 yuanes. Hay 3 rutas óptimas, el tiempo requerido es de 106 minutos y el número de traslados es 2;

El costo mínimo desde la estación de inicio S0087 hasta el destino final S3676 es de 3 yuanes. La ruta óptima con menor costo es 12, el tiempo requerido es 46 minutos y el número de transbordos es 2;

La ruta óptima con menor costo se muestra en las Tablas 6.1 y 6.2.

6.2.1 Establecimiento del modelo 2

Este modelo tiene como objetivo el problema 2, considerando autobuses y metros al mismo tiempo, encontrando rutas factibles y luego encontrando la ruta óptima. Para las líneas de metro, también puedes utilizarlas como líneas de autobús. Básicamente no hay diferencia, excepto que la tarifa, el tiempo y el tiempo de traslado son diferentes. Por tanto, una estación de metro puede equivaler a una estación de autobuses, y la estación de transferencia entre el metro y el autobús puede utilizarse como punto de intersección entre los dos. Por lo tanto, el modelo de ruta de transferencia de autobús de este modelo es básicamente el mismo que el del Modelo 1. Ahora establezca el modelo de ruta óptimo según el modelo 2.

1) Un modelo que toma la ruta con el menor tiempo como ruta óptima: el tiempo total de una ruta factible es el tiempo que tarda el autobús (autobús y metro) y el tiempo de traslado entre autobús y metro. , entre autobuses y entre metros La suma de los tiempos de transferencia.

(Fórmula 6.5)

Entre ellas, la k-ésima ruta es una o más de las rutas de transferencia de autobús y metro.

2) Un modelo que toma la ruta con menos transbordos como ruta óptima:

(Fórmula 6.6)

Este modelo es equivalente al transbordo anterior ruta Considere en orden de prioridad: directo, un transbordo o dos transbordos (incluidos los transbordos entre autobuses y metros).

3) Un modelo que toma la ruta de menor coste como ruta óptima: el coste de una ruta factible es la suma de los costes del autobús y del metro.

(Fórmula 6.7)

Entre ellos, todavía satisface (Fórmula 6.4).

6.2.2 Solución al modelo 2

No es difícil encontrar que el problema 1 es parte de la solución al problema 2. En el problema dos, la solución óptima recién generada proviene principalmente de la ruta mediante transbordo al metro y transbordo a estaciones similares cercanas, como se muestra en la siguiente figura:

Del punto A al B, figura (a) representa una transferencia a través de las estaciones de autobús adyacentes S1 y S2 en dos líneas de autobús; la figura (b) representa una transferencia secundaria usando una estación de metro; la figura (c) representa una transferencia usando otra línea de autobús como segunda transferencia;

La introducción de líneas ferroviarias ha aumentado la dificultad de resolver el problema. Para comprender visualmente la relación de intersección entre los dos ferrocarriles, hicimos la relación posicional de los dos ferrocarriles a través de la programación matlab (ver el. apéndice del programa) Figura, como se muestra en la Figura 6.3.

Figura 6.3 Diagrama de relación de ubicación de las vías ferroviarias T1 y T2

Nota: La línea recta en la Figura 4 representa la línea ferroviaria T1, el círculo representa la línea ferroviaria T2 y el valor numérico representa la estación, por ejemplo, 1 representa la estación de tren T1. La estación de tren D1 de la línea, 26 representa la estación de tren D26 de la línea ferroviaria T2. Esta imagen es consistente con el diagrama del metro de Beijing que se encuentra en línea (que se muestra en la Figura 6.4).

Figura 6.4 Diagrama esquemático del metro de Beijing

De manera similar, las líneas de metro son equivalentes a líneas de autobús para obtener rutas factibles entre dos estaciones cualesquiera, y luego las funciones objetivo se modelan usando Model 2. Expresión de expresión, use VC para programar (consulte el apéndice del programa) para encontrar la ruta óptima considerando la situación del metro.

1) La ruta óptima con el número mínimo de transbordos como objetivo

El número mínimo de transbordos desde la estación inicial S0008 a la estación final S0073 es 1, y el número mínimo de transbordos es Hay 1 ruta óptima;

El número mínimo de transbordos desde la estación inicial S0087 a la estación final S3676 es 0, es decir, hay una ruta directa y hay 1 ruta óptima directa ;

El número mínimo de transbordos desde la estación inicial S0148 a la estación final S0485 es 2, y hay 10 rutas óptimas con el menor número de transbordos;

La estación inicial S0971 a la estación final S0485 El número mínimo de transbordos es 2, y hay 20 rutas óptimas con el menor número de transbordos (nota 10 de ellas se enumeran en la Tabla 6.4);

El número mínimo de transbordos desde desde la estación inicial S1557 hasta la estación final S0481 El número de viajes es 2 y hay 17 rutas óptimas con la menor cantidad de transbordos (10 de ellas se enumeran en la Tabla 6.4);

El número mínimo de transbordos desde el inicio estación S3359 hasta el destino final S1828 es 2 veces, hay 2 rutas óptimas con el menor número de transbordos.

2) La ruta óptima con el menor consumo de tiempo como objetivo

El tiempo desde la estación inicial S3359 hasta la estación final S1828 es de al menos 64 minutos. La ruta óptima con el. consume menos tiempo (Hay 28 rutas (con menos transbordos y menos costo) (Nota: la Tabla 6.1 selecciona 10 de ellas para su representación);

El tiempo mínimo requerido desde la estación inicial S1557 hasta la estación final S0481 es de 109 min, 17 de las rutas óptimas con el menor consumo de tiempo son las mismas que la ruta óptima con el menor número de transbordos;

El tiempo desde la estación inicial S0971 hasta la estación final S0485 es al menos 96 min, y el que consume menos tiempo es 96 min. Hay 20 rutas óptimas que son iguales a la ruta óptima con el menor número de transbordos;

El tiempo desde la estación inicial S0008 hasta la estación final. S0073 es de al menos 55 minutos y hay 3 rutas óptimas que consumen menos tiempo;

El tiempo desde la estación inicial S0148 hasta la estación final S0485 es de al menos 87,5 minutos y 10 de las rutas óptimas son. las que consumen menos tiempo son las mismas que las rutas óptimas con el menor número de transbordos;

Se necesitan al menos 33 minutos desde la estación inicial S0087 hasta la estación final S3676. Una de las rutas óptimas con menos tiempo. el tiempo es el mismo que la ruta óptima con la menor cantidad de transbordos;

3) Costo mínimo La ruta óptima

El costo mínimo desde la estación inicial S3359 hasta la estación final S1828 es 3 yuanes La ruta óptima con el menor costo (la ruta con menor tiempo y menos transbordos) es 2

El costo mínimo desde la estación de inicio S1557 hasta el destino final S0481 es 3 yuanes, y hay 17 rutas óptimas. con el menor costo;

La estación de partida S0971 es el destino final. El costo mínimo de S0485 es de 5 yuanes, y hay 20 rutas óptimas con el menor costo;

El mínimo. El costo desde la estación inicial S0008 hasta el destino final S0073 es de 2 yuanes, y hay 1 ruta óptima con el menor costo;

El costo mínimo desde la estación inicial S0148 hasta la estación final S0485 es de 5 yuanes. , y hay 10 rutas óptimas con el menor costo;

Desde la estación inicial S0087 hasta la estación final S3676 El costo mínimo es 2 yuanes y hay 1 ruta óptima con el menor costo;

En este caso, solo consideramos la situación en la que puedes hacer transbordo a través de la estación de metro, y la situación en la que no pasas por la estación de metro es el resultado de la solución del Modelo 1. Los resultados de la solución del Modelo 2 se muestran en el Apéndice 1.

6.3.1 Establecimiento del Modelo 3

Este modelo aborda la pregunta 3 y tiene en cuenta la marcha, que es más realista. Porque cuando hay pocas paradas entre el punto de salida y el punto de transferencia, la estación terminal o la estación de transferencia, por supuesto es mejor optar por caminar para este tramo.

Por lo tanto, se hacen los siguientes supuestos:

1 Si existe una determinada ruta, el número de estaciones entre sus dos puntos finales es menor o igual a 2 (es decir. , pasa por un máximo de 4 estaciones), luego elija el método de caminata para llegar a su destino. Otras situaciones son manejadas por el Modelo 2. El número de paradas entre los dos puntos finales de la ruta se determina en función de la ruta de transferencia directa del autobús.

2. El tiempo medio de caminata entre las estaciones de autobuses adyacentes (incluidas las estaciones de metro) es de 5 minutos.

3. Si eliges caminar en una línea de autobús, el número de transbordos entre autobuses se reducirá en 1; si eliges caminar en una línea de metro, el número de transbordos entre metros se reducirá. por 1, excepto líneas directas.

El diagrama esquemático de los tramos a pie para rutas directas y de uno y dos transbordos se muestra en la Figura 6.5. (a) en la figura indica que se puede llegar directamente al punto de partida A y a la terminal B, y el número de estaciones separadas es igual a 2, por lo que elijo caminar (b) en la figura indica que el punto de partida A; y se puede llegar a la terminal B mediante un transbordo, en el que el tramo AC El número de estaciones es igual a 2, por lo que se elige caminar de manera similar, si el número de estaciones en el tramo CB es menor a 2, también se adopta caminar. La base para elegir el modo de caminar en (c) de la figura es similar.

Figura 6.5 Diagrama de caminata

La función de elegir el modo de caminar:

(Fórmula 6.8)

Representa el autobús mth ruta Si se debe caminar, indica si se debe caminar en la enésima línea de metro

Para rutas directas, si el número de estaciones entre el punto de partida y la terminal es menor o igual a 2, entonces camine, de lo contrario. tomar el autobús. El modelo de ruta óptimo para rutas que requieren transferencias se analiza a continuación:

1) La ruta más corta se utiliza como modelo de ruta óptima: el tiempo total de la ruta es igual al tiempo de viaje más el tiempo de caminata, más el traslado. veces.

(Fórmula 6.9)

Entre ellos, la k-ésima ruta es una o más de las rutas de transferencia de autobús y metro.

2) La ruta con el menor número de transbordos se utiliza como modelo de ruta óptimo: cada vez que caminas, necesitas transferir un coche menos.

(Fórmula 6.20)

Este modelo es equivalente a la prioridad de las rutas de transbordo anteriores según transbordos directos, uno, dos y tres (incluidos los transbordos entre autobuses y metros) Considere la orden.

3) El modelo que toma la ruta de menor coste como ruta óptima:

(Fórmula 6.21)

Entre ellos, aún satisface (Fórmula 6.4 ).

Las ventajas, desventajas y mejoras de los siete modelos

Evaluación del modelo 7.1

7.1.1 Ventajas del modelo

1. El modelo se compone de elementos simples. La complejidad se construye paso a paso, acercándolo a la realidad.

2. El modelo de este artículo es simple, su algoritmo es intuitivo y fácil de programar.

3. El modelo de este artículo presta más atención a los métodos de procesamiento y almacenamiento de datos, lo que mejora enormemente la eficiencia de las consultas.

4. El modelo de este artículo se centra en mejorar la eficiencia. Al extraer una gran cantidad de información de características y combinarla con algoritmos efectivos, puede cumplir plenamente con los requisitos de los sistemas en tiempo real.

7.1.2 Desventajas del modelo

En el proceso de modelado y programación, los datos utilizados son sólo una aproximación de los datos reales, por lo que los resultados obtenidos pueden ser algo diferentes a los reales. situación.

7.2 Mejora del modelo

El modelo anterior comienza principalmente desde las líneas de autobús, busca las intersecciones de las líneas de autobús como estaciones de transferencia y luego descubre los posibles viajes que pasan por dos estaciones cualesquiera. También podemos comenzar desde la perspectiva de las estaciones de autobuses y usar la teoría de grafos para construir un gráfico ponderado dirigido (como se muestra en la Figura 7.1). Este gráfico ponderado dirigido es un modelo de teoría de grafos establecido para la pregunta tres. este modelo. La Figura 7.1 representa el número de línea de autobús, que es la línea de enlace ascendente o descendente de la línea de autobús, , , , son los números de estación en la línea de autobús que representan el número de línea de metro, , . , , son los números de las estaciones de la línea de metro. Los autobuses y el metro se pueden transferir entre estaciones de autobuses y estaciones de metro. Si la línea de metro de la Figura 7.1 se reemplaza por una línea de autobús, para expresar el tiempo o costo requerido para hacer transbordo entre autobuses, la misma estación de transferencia debe estar representada por dos estaciones.

Figura 7.1 Gráfico ponderado dirigido de líneas de autobús

Según diferentes objetivos, se asignan diferentes pesos a los bordes entre diferentes estaciones. Luego utilice algoritmos relevantes de la teoría de grafos para encontrar el camino más corto correspondiente.

1) Al tomar el tiempo más corto como objetivo, asigne un peso de tiempo a cada borde. Al asignar un valor al borde entre dos estaciones cualesquiera en la misma línea, su peso es igual al producto del número de segmentos de línea de autobús entre las estaciones y el tiempo promedio. Cuando el número de estaciones entre dos tramos de una determinada línea es menor o igual a 3, se elige caminar, y el peso de la línea es igual al tiempo de caminata. Al realizar transferencias entre diferentes autobuses y metros, se deben asignar diferentes pesos para representar el tiempo de transferencia.

Por ejemplo (como se muestra en la Figura 7.1):

Cuando jgt; 4, el peso del borde de to;,

No es necesario transferir desde hasta, pero de acuerdo con Suponga que debe elegir caminar, y su peso de borde es;,

Desde hasta, puede tomar el autobús, luego hacer transbordo o caminar, según el supuesto de caminar. el número de intervalos de estación es menor que 2, por lo que elige caminar y su borde Peso;,

Cuando ggt;4, el peso del borde entre y;,

El peso del borde de;

El peso del borde de Valor;

Cuando jgt;4,ggt;4, la longitud de la ruta es:

;

Cuando,ggt;4, entonces la longitud del camino desde hasta Elija caminar y luego tomar el metro. La longitud del camino es;

Después de encontrar la longitud del camino de la ruta factible entre dos cualesquiera; puntos, luego busque la ruta factible del camino más corto como la ruta de tiempo óptima.

2) Cuando el objetivo es minimizar el costo, asigne un peso de costo a cada borde.

Los pesos de los bordes entre las paradas de autobús se asignan según (fórmula 6.4).

Cuando la línea de autobús se cobra con una tarifa única, para dos paradas cualesquiera y entre ellas,

Si, entonces elige caminar si, entonces;

Cuando la línea de autobús se cotiza por sección, si, entonces; si, entonces; si, entonces;

Si, entonces elija caminar entre dos estaciones cualesquiera de la línea de metro; entonces; los pesos de los bordes entre el sitio de transferencia y son todos 0, es decir, entonces la longitud del camino de una ruta factible desde el sitio de transferencia hasta es:

Si, entonces elija desde Caminar, ;

Si, entonces;

También puede encontrar la longitud de la ruta factible entre dos puntos cualesquiera y luego buscar la ruta más corta como la ruta óptima con costo.