Apresentação

A FCT Entregas é uma pequena empresa de logística recém-chegada à movimentada cidade de NP-Completópolis. Apesar do entusiasmo e da dedicação de seus fundadores, a empresa enfrenta sérias dificuldades para se destacar no mercado local.

A concorrência é intensa, os clientes ainda são poucos, e a organização das rotas de entrega tem se mostrado ineficiente. Com isso, os recursos disponíveis não estão sendo aproveitados da melhor maneira.

Buscando mudar esse cenário, a FCT Entregas decidiu recorrer à sua equipe especializada em otimização de rotas e soluções logísticas. O desafio é claro: transformar o sistema de entregas da empresa em uma operação eficiente, confiável e capaz de conquistar novos clientes em NP-Completópolis.

O mapa da cidade está repleto de pontos de interesse, que representam desde locais de coleta e entrega de pedidos até potenciais clientes. A missão é criar rotas otimizadas para cada entregador, garantindo que:

• Todos os pedidos do dia sejam atendidos rigorosamente;
• Todos os pontos sejam visitados, mesmo que não representem pedidos;
• Cada ponto seja visitado apenas uma vez e por apenas um entregador;
• Cada entregador percorra uma rota fechada, retornando à sede da empresa;
• Ao visitar a sede, o entregador finaliza sua rota, não podendo mais visitar outros pontos;
• Sempre que o entregador visitar um ponto de coleta, ele deve adicionar o pedido à sua bolsa;
• A capacidade de carga de cada entregador nunca seja excedida;
• Todos os entregadores devem ser utilizados, com cada um realizando ao menos uma entrega;

Com essas diretrizes, espera-se que a nova estratégia logística proporcione à FCT Entregas uma vantagem competitiva em NP-Completópolis.

Descrição do problema

Você deve desenvolver um programa que leia a especificação do desafio, via stdin, obtenha o plano para a conclusão do mapa lido, e gere uma saída, via stdout, no formato especificado na descrição do trabalho. Caso não encontre um plano, encerre seu programa com um exit(120).

Dado:

• Um conjunto $G$ com $n$ pontos, identificados por $z_i$ e suas coordenadas ${xᵢ, yᵢ}$;
• Um conjunto $P$ com $m$ pedidos, identificados por $w_i$, que devem ser entregues do ponto $O_i$ ao ponto $D_i$.

Defina as rotas para $E$ entregadores, cada um com capacidade máxima $L$, de modo a minimizar a soma total dos custos de viagem de cada entregador, respeitando as restrições mencionadas.

O custo de viagem $C_{ij}$ entre dois pontos é dado por:

$C_{ij} = \lfloor \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} \rfloor$

Ferramentas e auxiliares

Esta seção descreve as várias ferramentas auxiliares disponíveis para resolver o problema. As ferramentas estão organizadas em categorias: planejadores PDDL, planejadores HDDL, SAT-solvers e bibliotecas auxiliares. A localização e a forma de chamada de cada ferramenta estão descritas a seguir.

Planejadores PDDL

Para utilizar dos planejadores PDDL, você precisará de um modelo PDDL do problema, criar os arquivos de domínio e problema PDDL correspondentes, chamar o planejador selecionado com os parâmetros corretos. Aqui estão os planejadores PDDL disponíveis:

1. Planejadores Madagascar (M, Mp, MpC):
   • Localização: /home/software/planners/madagascar/{M,Mp,MpC}.
2. Fast Downward:
   • Localização: /home/software/planners/downward/fast-downward.py.
   • Localização: /home/software/planners/downward-fdss23/fast-downward.py.
   • Localização: /home/software/planners/scorpion-maidu/fast-downward.py.
3. Planejador em Julia:
   • Localização: /home/software/planners/julia/planner.jl.

Planejadores HDDL

Para utilizar dos planejadores HDDL, você precisará de um modelo HDDL do problema, crie os arquivos de domínio e problema HDDL correspondentes, chame o planejador selecionado com os parâmetros corretos. Aqui estão os planejadores HDDL disponíveis:

1. Panda:
   • Localização: /home/software/planners/panda/panda.jar.
2. PandaPI:
   • Localização: /home/software/planners/pandaPI/pandasolver.

SAT-solvers

Para utilizar dos SAT-solvers, você precisará de uma formulação do problema em forma de CNF (Conjunctive Normal Form). Aqui estão os SAT-solvers disponíveis e como utilizá-los:

1. Clasp:
   • Localização: /usr/bin/clasp.
2. CryptoMiniSat:
   • Localização: /usr/bin/cryptominisat.
3. MiniSat:
   • Localização: /usr/bin/minisat.
     • Submissões feitas em C++ serão compiladas com -lminisat
4. MiniSat+:
   • Localização: /usr/bin/minisat+.
5. PackUp:
   • Localização: /usr/bin/packup.
6. PicoSAT:
   • Localização: /usr/bin/picosat.
7. SAT4J:
   • Localização: /usr/bin/sat4j.
8. Python-SAT:
   • https://pysathq.github.io/docs/html.
9. Z3
   • Localização: /usr/bin/z3

Como classificar nesta modalidade

Nesta modalidade de classificação, o problema é dividido em três categorias: AGILE, SATISFICING e OPTIMAL. A pontuação é computada da seguinte forma:

• Categoria AGILE:
  • A pontuação é obtida pela fórmula $1-log(TEMPO\_DE\_EXECUCAO) / log(30)$.
  • Se o tempo de execução for menor ou igual a $1$ segundo, a pontuação é $1$.
  • A track tem um time limit de $30$ s.
• Categoria SATISFICING:
  • A pontuação é calculada pela fórmula $C^*/C$, onde $C^*$ é o custo do plano de referência e $C$ é o custo do plano encontrado.
  • Quanto menor for o custo do plano encontrado em relação ao plano de referência, melhor será a pontuação.
  • A track tem um time limit de $180$ s.
• Categoria OPTIMAL:
  • O objetivo é responder o plano ótimo.
  • O desempenho é avaliado pela corretude do plano e não pela pontuação.
  • A track tem um time limit de $180$ s.

Entrada

1. Primeira linha: quatro inteiros $e$, $n$, $p$ e $q$:
   • $e$: número de entregadores
   • $n$: número de pontos no mapa
   • $p$: número de pedidos solicitados
   • $q$: capacidade máxima dos entregadores
2. Próximas $n$ linhas: três inteiros $z$, $x$, $y$:

   • $z$: identificador do ponto

   • $x$, $y$: coordenadas cartesianas

   • Obs.: O ponto com identificador 0 é a sede da empresa (ponto onde devem-se iniciar e terminar as rotas).

3. Próximas $p$ linhas: três inteiros $w$, $o$, $d$:
   • $w$: identificador do pedido
   • $o$: ponto de origem
   • $d$: ponto de destino

Saída

Para cada entregador $e$, imprimir:

1. Número $t$ de pontos visitados;
2. $t$ linhas com o identificador $z$ de cada ponto visitado, na ordem de visitação;
3. Número $s$ de pedidos entregues;
4. $s$ linhas com o identificador $w$ de cada pedido entregue;
5. Um inteiro $T$, o custo total da viagem.

Exemplo

Exemplo de entrada 1

2 8 2 2
0 150 30
1 400 200
2 200 10
3 48 100
4 150 170
5 42 320
6 200 30
7 400 420
1 1 2
2 5 4

Saída para o exemplo

5
3
7
5
4
0
1
2
1293
4
1
2
6
0
1
1
647

1. Explicação para a saída do exemplo

   A saída acima representa as rotas, as entregas feitas e o custo da rota por entregador, neste caso:

   • Entregador 1:
     • Rota: 0 → 3 → 7 → 5 → 4 → 0
     • Entregues: Pedido 2
     • Custo total: 1293
   • Entregador 2:
     • Rota: 0 → 1 → 2 → 6 → 0
     • Entregues: Pedido 1
     • Custo total: 647

Teste você mesmo