Encuentre la mejor combinación de un conjunto determinado de conjuntos múltiples

https://stackoverflow.com/questions/14884

08-06-2019
|

Pregunta

Digamos que tienes un envío.Debe ir del punto A al punto B, del punto B al punto C y finalmente del punto C al punto D.Necesitas que te llegue en cinco días por la menor cantidad de dinero posible.Hay tres posibles transportistas para cada tramo, cada uno con su propio tiempo y costo diferentes para cada tramo:

Array
(
    [leg0] => Array
        (
            [UPS] => Array
                (
                    [days] => 1
                    [cost] => 5000
                )

            [FedEx] => Array
                (
                    [days] => 2
                    [cost] => 3000
                )

            [Conway] => Array
                (
                    [days] => 5
                    [cost] => 1000
                )

        )

    [leg1] => Array
        (
            [UPS] => Array
                (
                    [days] => 1
                    [cost] => 3000
                )

            [FedEx] => Array
                (
                    [days] => 2
                    [cost] => 3000
                )

            [Conway] => Array
                (
                    [days] => 3
                    [cost] => 1000
                )

        )

    [leg2] => Array
        (
            [UPS] => Array
                (
                    [days] => 1
                    [cost] => 4000
                )

            [FedEx] => Array
                (
                    [days] => 1
                    [cost] => 3000
                )

            [Conway] => Array
                (
                    [days] => 2
                    [cost] => 5000
                )

        )

)

¿Cómo harías para encontrar la mejor combinación mediante programación?

Mi mejor intento hasta ahora (tercer o cuarto algoritmo) es:

Encuentre el cargador más largo para cada tramo
Elimina el más "caro"
Encuentra el transportista más barato para cada tramo
Calcular el costo total y los días.
Si los días son aceptables, termine; de lo contrario, vaya a 1.

Rápidamente simulado en PHP (tenga en cuenta que la matriz de prueba a continuación funciona a la perfección, pero si la prueba con la matriz de prueba anterior, no encuentra la combinación correcta):

$shippers["leg1"] = array(
    "UPS"    => array("days" => 1, "cost" => 4000),
    "Conway" => array("days" => 3, "cost" => 3200),
    "FedEx"  => array("days" => 8, "cost" => 1000)
);

$shippers["leg2"] = array(
    "UPS"    => array("days" => 1, "cost" => 3500),
    "Conway" => array("days" => 2, "cost" => 2800),
    "FedEx"  => array("days" => 4, "cost" => 900)
);

$shippers["leg3"] = array(
    "UPS"    => array("days" => 1, "cost" => 3500),
    "Conway" => array("days" => 2, "cost" => 2800),
    "FedEx"  => array("days" => 4, "cost" => 900)
);    

$times = 0;
$totalDays = 9999999;

print "<h1>Shippers to Choose From:</h1><pre>";
print_r($shippers);
print "</pre><br />";

while($totalDays > $maxDays && $times < 500){
            $totalDays = 0;
            $times++;
            $worstShipper = null;
            $longestShippers = null;
            $cheapestShippers = null;

            foreach($shippers as $legName => $leg){
                //find longest shipment for each leg (in terms of days)
                unset($longestShippers[$legName]);
                $longestDays = null;        

                if(count($leg) > 1){
                    foreach($leg as $shipperName => $shipper){
                        if(empty($longestDays) || $shipper["days"] > $longestDays){
                            $longestShippers[$legName]["days"] = $shipper["days"];
                            $longestShippers[$legName]["cost"] = $shipper["cost"];
                            $longestShippers[$legName]["name"] = $shipperName;
                            $longestDays = $shipper["days"];
                        }
                    }           
                }
            }

            foreach($longestShippers as $leg => $shipper){
                $shipper["totalCost"] = $shipper["days"] * $shipper["cost"];

                //print $shipper["totalCost"] . " &lt;?&gt; " . $worstShipper["totalCost"] . ";";

                if(empty($worstShipper) || $shipper["totalCost"] > $worstShipper["totalCost"]){
                    $worstShipper = $shipper;
                    $worstShipperLeg = $leg;
                }
            }

            //print "worst shipper is: shippers[$worstShipperLeg][{$worstShipper['name']}]" . $shippers[$worstShipperLeg][$worstShipper["name"]]["days"];
            unset($shippers[$worstShipperLeg][$worstShipper["name"]]);

            print "<h1>Next:</h1><pre>";
            print_r($shippers);
            print "</pre><br />";

            foreach($shippers as $legName => $leg){
                //find cheapest shipment for each leg (in terms of cost)
                unset($cheapestShippers[$legName]);
                $lowestCost = null;

                foreach($leg as $shipperName => $shipper){
                    if(empty($lowestCost) || $shipper["cost"] < $lowestCost){
                        $cheapestShippers[$legName]["days"] = $shipper["days"];
                        $cheapestShippers[$legName]["cost"] = $shipper["cost"];
                        $cheapestShippers[$legName]["name"] = $shipperName;
                        $lowestCost = $shipper["cost"];
                    }
                }

                //recalculate days and see if we are under max days...
                $totalDays += $cheapestShippers[$legName]['days'];  
            }
            //print "<h2>totalDays: $totalDays</h2>";
        }

        print "<h1>Chosen Shippers:</h1><pre>";
        print_r($cheapestShippers);
        print "</pre>";

Creo que tal vez tenga que hacer algún tipo de cosa en la que literalmente haga cada combinación una por una (con una serie de bucles) y sume la "puntuación" total de cada una, y encuentre la mejor...

EDITAR:Para aclarar, esta no es una "tarea" (no estoy en la escuela).Es parte de mi proyecto actual en el trabajo.

Los requisitos (como siempre) han ido cambiando constantemente.Si me dieran las restricciones actuales en el momento en que comencé a trabajar en este problema, estaría usando alguna variante del algoritmo A* (o el camino más corto de Dijkstra o simplex o algo así).Pero todo se ha ido transformando y cambiando, y eso me lleva a donde estoy ahora.

Así que supongo que eso significa que necesito olvidarme de toda la basura que he hecho hasta este momento y simplemente seguir con lo que sé que debo usar, que es un algoritmo de búsqueda de ruta.

Solución

Podría alterar algunas de las algoritmos de camino más corto, como el de Dijkstra, para ponderar cada camino por costo pero también realizar un seguimiento del tiempo y dejar de seguir un camino determinado si el tiempo excede su umbral.Deberías encontrar el más barato que te permita estar por debajo de tu umbral de esa manera.

Otros consejos

Parece que lo que tienes se llama "problema de programación lineal".También suena como un problema de tarea, sin ofender.

La solución clásica a un problema de PL se llama "Método Simplex".Buscalo en Google.

Sin embargo, para utilizar ese método, debe tener el problema correctamente formulado para describir sus requisitos.

Aún así, es posible enumerar todas las rutas posibles, ya que tiene un conjunto muy pequeño.Sin embargo, algo así no escalará.

Suena como un trabajo para algoritmo de dijkstra:

El algoritmo de Dijkstra, concebido por el informático holandés Edsger Dijkstra en 1959, 1 es un algoritmo de búsqueda de gráficos que resuelve el problema de la ruta más corta de una sola fuente para un gráfico con costos de ruta de borde no negativos, generando un árbol de ruta más corta.Este algoritmo se utiliza a menudo en el enrutamiento.

También hay detalles de implementación en el artículo de Wikipedia.

Si supiera que sólo tengo que tratar con 5 ciudades, en un orden predeterminado, y que sólo hay 3 rutas entre ciudades adyacentes, lo haría con fuerza bruta.No tiene sentido ser elegante.

Si, por otro lado, esto fuera una tarea y se supusiera que tuviera que producir un algoritmo que realmente pudiera escalar, probablemente adoptaría un enfoque diferente.

Como dijo Baltimark, esto es básicamente un problema de programación lineal.Si solo los coeficientes de los transportistas (1 para incluidos, 0 para no incluidos) no fueran números enteros (binarios) para cada tramo, esto sería más fácil de resolver.Ahora necesita encontrar algunas heurísticas de programación lineal entera (ILP) (binaria), ya que el problema es NP-difícil.Ver Wikipedia sobre programación lineal entera para enlaces;en mi curso de programación lineal usamos al menos Rama y atado.

En realidad, ahora que lo pienso, este caso especial se puede resolver sin ILP real ya que la cantidad de días no importa siempre que sea <= 5.Ahora comience eligiendo la aerolínea más barata como primera opción (Conway 5:1000).A continuación eliges una vez más el más barato, lo que da como resultado 8 días y 4000 unidades monetarias, lo cual es demasiado, así que lo abortamos.Al probar otros también, vemos que todos los resultados son días > 5, por lo que volvemos a la primera opción y probamos la segunda más barata (FedEx 2:3000) y luego subimos en la segunda y Fedex en la última.Esto nos da un total de 4 días y 9000 unidades monetarias.

Luego podríamos usar este costo para podar otras búsquedas en el árbol que, según algún resultado de etapa de subárbol, costarían más que el que ya hemos encontrado y dejar ese subárbol sin buscar a partir de ese momento.Esto sólo funciona mientras sepamos que la búsqueda en el subárbol no producirá mejores resultados, como ocurre aquí cuando los costos no pueden ser negativos.

Espero que esta divagación haya ayudado un poco :).

Esto es un problema de mochila.Los pesos son los días en tránsito y la ganancia debe ser de $5000: costo del tramo.¡Elimine todos los costos negativos y continúe desde allí!

Creo que el algoritmo de Dijkstra sirve para encontrar el camino más corto.

cmcculloh está buscando el costo mínimo sujeto a la restricción de que lo recibe en 5 días.

Por lo tanto, simplemente encontrar la manera más rápida no lo llevará allí más barato, y llegar allí por el más barato no lo llevará allí en el tiempo requerido.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow