Chargement efficace des bus

C'est quelque chose que j'ai fait pour une entreprise de voyages en bus il y a longtemps et je n'ai jamais été satisfait des résultats. Je pensais à cet ancien projet récemment et pensais que je reverrais ce problème.

Problème:

La société de voyages en bus dispose de plusieurs bus avec des capacités de passagers différentes (par exemple 15 bus de 50 passagers, 25 bus de 30 passagers ... etc.). Ils se sont spécialisés dans l'offre de transport à de très grands groupes (300+ passagers par groupe). Étant donné que chaque groupe doit voyager ensemble, il lui fallait gérer efficacement sa flotte pour réduire les déchets.

Par exemple, 88 passagers sont mieux desservis par trois bus de 30 passagers (2 sièges vides) que par deux bus de 50 passagers (12 sièges vides). Autre exemple, 75 passagers seraient mieux desservis par un bus de 50 passagers et un bus de 30 passagers, un mélange de types.

Quel est un bon algorithme pour le faire?

Ceci est (en quelque sorte) un exemple du problème d'emballage de bacs, qui est souvent confondu avec le problème du sac à dos. Dans l'emballage des bacs, vous avez des bacs d'une certaine capacité et vous essayez de distribuer des objets de différentes tailles dans les bacs. L'idée est d'utiliser le moins de bacs possible.

Vous n'essayez pas exactement de minimiser le nombre de bacs, cependant, vous essayez de minimiser le nombre de sièges vides. Et il est possible que vous essayiez de minimiser le nombre de sièges vides dans toute la flotte, c'est-à-dire que vous avez quatre groupes touristiques de différentes tailles, et que vous souhaitiez tous les accueillir avec le moins de sièges vides. Je ne peux pas penser à une instance dès le départ, mais j'imagine qu'il pourrait être possible de construire une flotte et un ensemble de groupes de tournée de telle sorte que vous seriez mieux avec une solution de qualité inférieure pour certains groupes, car cela vous a permis d'éviter en utilisant une solution encore pire pour un autre groupe.

Ça s'empire. Et si vous avez 20, 30 et 50 bus de passagers. Chacun utilise différentes quantités de carburant, mais il est plus efficace de faire fonctionner un 50 que de faire fonctionner un 20 et un 30. Mais d'après notre mesure unique (le moins de sièges vides), il est logique de courir soit pour un 50 visite des passagers.

De plus, les bus avec des numéros étranges, comme 28 ou 39, dévieraient beaucoup de nos raccourcis.

Donc, selon la complexité de la situation, vous pouvez faire l'une des deux choses suivantes:

Premier arbre de recherche exhaustif: utilisez toutes les combinaisons possibles de bus. Si vous n'avez que 3 ou 4 tailles de bus, c'est probablement une solution raisonnable. Sinon, quelque chose comme Meilleur ajustement décroissant donnerait des résultats raisonnables, mais pas optimaux.

Voici une solution rapide et sale en Python:

def add50(passengers, buses):
    proposed = buses + [50]
    if sum(proposed) < passengers:
        return add50(passengers, proposed)
    return proposed

def add30(passengers, buses):
    proposed = buses + [30]
    if sum(proposed) < passengers:
        proposed30 = add30(passengers, proposed)
        proposed50 = add50(passengers, proposed)
        return proposed30 if sum(proposed30) < sum(proposed50) else proposed50
    return proposed

print add30(88, [])
print add30(75, [])
print add30(105, [])

Quand je l'exécute, j'obtiens:

[30, 30, 30]
[30, 50]
[30, 30, 50]

Le code effectue une recherche approfondie dans les scénarios possibles. Puisque l'ordre n'a pas d'importance ( [30, 50]est le même que [50, 30]), nous pouvons rendre l'espace de recherche beaucoup plus petit en ajoutant uniquement des bus de même taille ou plus grands. C'est pourquoi add30()peut appeler add50(), mais pas l'inverse.

Je vais répondre à cela du point de vue du client. Je ne voudrais pas d'un algorithme codé en dur pour cette application. Il y a trop de variables qui peuvent changer avec le temps. Bien que rien dans vos bus ne puisse changer le poids des facteurs, cela pourrait changer ou de nouveaux facteurs pourraient être découverts auxquels je n'ai jamais pensé (par exemple, le temps, les lois et les autres coûts de conduite).

Pour cette raison, je voudrais pouvoir créer ma propre table de recherche basée sur une plage du nombre de passagers demandé et je créerais mes propres paramètres pour les meilleures combinaisons de bus. Exemple: 31-50 = 1 X 50, 51-60 = 2 X 30. Faut-il vraiment le calculer? Plus facile à modifier les paramètres qu'un tas de formules prenant en compte les sièges, l'essence et les pilotes. Déterminez la meilleure combinaison et faites-en et laissez suffisamment de place à l'utilisateur pour modifier ces paramètres comme bon lui semble.

De nouveaux facteurs pourraient être découverts. Les gros bus paient-ils un tarif exponentiellement plus élevé sur les péages? Puis-je obtenir des chauffeurs moins chers pour les petits bus lorsqu'une nouvelle loi sur la certification et les licences supplémentaires s'applique aux conducteurs de bus de plus de 30 passagers?

Ils embauchent un nouveau consultant avec une logique différente de leur formule et votre application peut avoir besoin d'être réécrite. Vous voulez dire que vous devez prendre en compte le coût du stationnement?