Carregamento eficiente de barramento

Isso foi algo que fiz para uma empresa de viagens de ônibus há muito tempo e nunca fiquei feliz com os resultados. Eu estava pensando naquele projeto antigo recentemente e pensei em revisitar esse problema.

Problema:

A empresa de viagens de ônibus possui vários ônibus com diferentes capacidades de passageiros (por exemplo, 15 ônibus de 50 passageiros, 25 ônibus de 30 passageiros ... etc). Eles se especializaram em oferecer transporte para grupos muito grandes (mais de 300 passageiros por grupo). Como cada grupo precisa viajar juntos, eles precisam gerenciar sua frota com eficiência para reduzir o desperdício.

Por exemplo, 88 passageiros são mais bem servidos por três ônibus de 30 passageiros (2 lugares vazios) do que por dois ônibus de 50 passageiros (12 lugares vazios). Outro exemplo: 75 passageiros seriam melhor atendidos por um ônibus de 50 passageiros e um de 30 passageiros, uma mistura de tipos.

O que é um bom algoritmo para fazer isso?

Este é (mais ou menos) um exemplo do problema de empacotamento de lixeira, que freqüentemente é confundido com o problema da mochila. Na embalagem do compartimento, você tem compartimentos de certa capacidade e está tentando distribuir objetos de vários tamanhos nos compartimentos. A idéia é usar o menor número possível de posições.

Você não está exatamente tentando minimizar o número de caixas, mas tentando minimizar o número de assentos vazios. E é possível que você esteja tentando minimizar o número de assentos vazios em toda a frota, ou seja, tenha quatro grupos de excursões de vários tamanhos e deseje acomodar todos eles com o menor número de assentos vazios. Não consigo pensar em uma instância logo de cara, mas imagino que seja possível construir uma frota e um conjunto de grupos de turnês, para que você tenha uma solução abaixo do padrão para alguns grupos, porque isso permite que você evite usando uma solução ainda pior para outro grupo.

Fica pior. E se você tiver 20,30 e 50 ônibus de passageiros. Cada um usa quantidades diferentes de combustível, mas é mais eficiente rodar um 50 do que rodar 20 e 30. Mas, em nossa única medida (menor número de assentos vazios), faz sentido rodar por 50 passeio de passageiros.

Além disso, ônibus com números estranhos, como 28 ou 39, distorceriam muitos de nossos atalhos.

Portanto, dependendo da complexidade da situação, você pode fazer uma de duas coisas:

Primeiro, e árvore de pesquisa exaustiva: use todas as combinações possíveis de ônibus. Se você tiver apenas 3 ou 4 tamanhos de barramento, provavelmente esta é uma solução razoável. Caso contrário, algo como Melhor ajuste decrescente produziria resultados razoáveis, mas não ideais.

Aqui está uma solução rápida e suja no 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, [])

Quando o executo, recebo:

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

O código está fazendo uma pesquisa aprofundada nos possíveis cenários. Como a ordem não importa ( [30, 50]é a mesma que [50, 30]), podemos reduzir muito o espaço de pesquisa, adicionando apenas barramentos do mesmo tamanho ou maiores. É por isso que add30()pode ligar add50(), mas não o contrário.

Vou responder isso da perspectiva do cliente. Eu não gostaria de um algoritmo codificado para este aplicativo. Existem muitas variáveis ​​que podem mudar com o tempo. Embora nada em seus ônibus possa mudar o peso dos fatores, ou novos fatores que eu nunca tenha pensado (por exemplo, horas extras, leis e outros custos de motorista).

Por esse motivo, gostaria de poder criar minha própria tabela de pesquisa com base em um intervalo do número de passageiros solicitados e criar minhas próprias configurações para as melhores combinações de ônibus. Exemplo: 31-50 = 1 X 50, 51-60 = 2 X 30. Isso realmente precisa ser calculado? É mais fácil alterar as configurações do que um monte de fórmulas que incluem assentos, gasolina e motoristas. Descubra a melhor combinação, faça-a e tenha espaço de sobra para que o usuário altere essas configurações como achar melhor.

Novos fatores podem ser descobertos. Os ônibus maiores pagam uma taxa exponencialmente mais alta em pedágios? Posso obter motoristas menos caros para ônibus pequenos quando uma nova lei para certificação e licenciamento extras é aplicada a motoristas de ônibus com mais de 30 passageiros?

Eles contratam um novo consultor com uma lógica diferente de sua fórmula e seu aplicativo pode precisar ser reescrito. Quer dizer que você precisa calcular o custo do estacionamento?