**Edit** : Aceitar soluções não válidas e aplicar uma penalização.

# Notas para CheckPoint 1

## 1) Definição do problema

Num mapa x por y existem armazéns ...

## 2) Trabalhos relacionados

- Kaggle de 2020 com o problema de 2016, da Google: https://www.kaggle.com/c/hashcode-drone-delivery
- Solução de primeiro lugar usando Scala: https://www.kaggle.com/lyxthe/1st-place-solution | https://github.com/miraan/google-hash-code-qualification-round
- Segundo lugar, python: https://www.kaggle.com/royceda/drone-linear-prog-and-routing-heuristic-90-done
- Outra solução usando Python: https://www.kaggle.com/spacelx/2020-hc-dd-2nd-place-solution-w-or-tools

Problema é semelhante a um CVRP (Capacitated Vehicle Routing Problem)

- Google OR-Tools para VRP e CVRP: https://developers.google.com/optimization/routing/vrp | https://developers.google.com/optimization/routing/cvrp
- Também se adicionar "Pickup and deliveries": https://developers.google.com/optimization/routing/pickup_delivery
- LocalSolver : https://www.localsolver.com/benchmarkcvrp.html | https://www.localsolver.com/docs/last/exampletour/vrp.html

- CVRPPAD - https://link.springer.com/article/10.1007/s10479-017-2722-x | https://link.springer.com/content/pdf/10.1007/s10479-017-2722-x.pdf

- Genetic Algorithm :
- A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries (2011): https://www.sciencedirect.com/science/article/pii/S0360835211003482
- A vehicle routing problem solved by using a hybrid genetic algorithm (2007) [Gene WTF]: https://www.sciencedirect.com/science/article/pii/S0360835207001222
- Waiting strategy for the vehicle routing problem with simultaneous pickup and delivery using genetic algorithm (2020) [Bom Gene]: https://www.sciencedirect.com/science/article/pii/S0957417420307429
- Ainda para checkar (2005): https://www.sciencedirect.com/science/article/pii/S0952197607000887

## 3) Formulação do problema

### Representação da Solução

Node <- Indice do WareHouse ou indice da order

Dois tipos de alelos, entrega e _pick-up_. Entrega com valores de Demand a negativo e _pick-up_ com valores positivos.

Formação de soluções iniciais: Os alelos de entrega são obrigatórios, os de pick-up são até uma certain extent.

Criar solução inicial que obedeça a constraints e assegura que todas as orders são entregues, mesmo que fiquem com baixa pontuação:

P -> Product
Pq -> Quantidade de Produto
Pr -> Resto de Produto
WH -> WareHouse
WHn -> WareHouse node
A -> Alelo
Ap -> Alelo pickup
Ad -> Alelo Deliver
Dc -> Drone capacity
Da -> Lista de alelos deliver
Rp -> remainder product

-- Formar alelos:
-- Na criação de lista de alelos deliver, se mod(demand) > Dc, cria [2, inf] alelos 
-- para a mesma delivery com quantidades diferentes.

Da[] <- CreateList(Orders)
For each Ad in Da[]:
    Pr <- Ad.Quantity
    for WH in WH[]:
        If WH has P
            N <- calculateProduct(Pr) //available vs needed, updates Pr
            Ap <- alelo (_, Pq, WHn, N)
            Cromossoma.push(Ap)
            if Pr == 0:
                break
    Remove WH's with 0 products
    Cromossoma.push(Ad)

calculateProduct(needed):
    if available == needed
        internal value = 0
        needed = 0
        returns needed
    elif available > needed
        updates internal amount -> available - needed 
        needed = 0
        returns needed
    elif needed > available
        internal value = 0
        needed = needed - available
        returns needed
    
-- Formar cromossoma solution:

index <- 1
For each A in Cromossoma:
    assign drone with index
    if A is Deliver
        index++
    if index > nº Drones
        index <- 1

-- Para cada alelo de delivery, drone fica com alelos anteriores de pick up. 
-- Quando ficar sem drones recomeça.

:::info
Outra solução possivel, usando o método acima, começar pelos WH de indice superior.
:::

Soluções aleatórias (GA):

2 partes:
- Formação de alelos
- Formação de locus/genes

Cria-se configuração de alelos, tenta-se povoar locus x vezes. Se não der nenhuma solução fazível, forma-se outra configuração de alelos.

-- Na criação de lista de alelos deliver, se mod(demand) > Dc, 
-- cria [2, inf] alelos para a mesma delivery com quantidades diferentes.

WH[] <- Vai sendo modificada, retirando produtos e quantidades. 
Quando WH ficar vazio, retira-se da lista

while Da[] not empty
    if rdm() > 0.5 // adiciona Deliver allele
        Ad <- rdm(Da[])
        D <- rdm(Drone)
        if checkConstraints() || 0
            cromossoma.push(D,Ad)
    else 
        if WH[] empty
            continue
        WH <- rdm(WH[])
        P <- rdm(WH)
        Pq <- rdm(P[WH])
        D <- rdm(Drone) || 0
        if checkConstraint()
            cromossoma.push(D, Pq, WHn, P)

-- Pode acontecer de que vai sendo criada uma solução cuja qualquer adição não obedeça a constraints
-- Neste caso, ou se refaz a árvore, ou se retira n genes recentemente adicionados do cromossa (backtrack) e não se aplia o mesmo gene outra vez na mesma posição
-- also, pode-se adicionar um drone 0 em vez de um id válido, significa que esse gene fica disponivel para ser alcançado mas não tem um drone. Genes deliver também podem ter 0, já que todas as orders não precisam de ser completas

### Neighborhood/Mutation

#### Mutações nos cromossomas

- Trocar drones de 2 alelos para alterar trajetos (funciona com drones nulos)
- 2 alelos do mesmo WH e item -> desiquilibrar as quantidades
- Adiciona genes de Supply: Caso haja items em WH que não estão a ser picked up, adiciona esse gene com quantidade aleatória entre [1, min(Pq,Dc)] e drone nulo
- Junta 2 genes de deliver num mesmo, ficando na posição do primeiro, com um dos drones, escolhido aleatório
- Junta 2 genes de deliver num mesmo, ficando na posição do segundo, com um dos drones, escolhido aleatório
- Junta 2 genes de supplier num mesmo, ficando na posição do primeiro, com um dos drones, escolhido aleatório
- Junta 2 genes de supplier num mesmo, ficando na posição do segundo, com um dos drones, escolhido aleatório

#### Mutações nos genes

- Dividir um alelo de supplier em 2 com quantidades iguais
- Dividir um alelo de supplier em 2 com quantidades desiguais
- Pôr um gene com drone None

### Crossover functions


Provoca alterações nas rotas dos drones. Por exemplo, um drone que enche e só envia muito depois pode ficar livre mais cedo ou entregar mais perto.

### Rigid constraints

- Caminho de drone não pode ultrapassar os turnos previstos

Vendo os genes de cada drone
Começando no primeiro gene, busca o segundo e guarda os nós de cada
Calcula a distância entre os nós, adiciona 1
Guarda esse valor num somatório
Quando chegar ao último gene, acaba
Verifica se valor de somatório é < que nº de turnos

- Drone não pode ter mais carga que a capacidade/carga negativa

Vendo os genes de cada drone
CargaAtual <- 0
Por cada gene
    Atualiza valor da carga com o valor da demand
    Se carga atual for > carga drone ou < 0 -> not feasible

- Drone só pode entregar produtos que tem (id e quantidade)

Para cada drone
Para cada gene desse drone
  Atualiza lista de produtos (id's e quantidade) em cada gene
  Se entrega um produto que não possui -> not feasible

- X Drone não pode retirar de um armazém mais quantidade do que a que o WH tem disponivel

Vendo os genes de cada armazém
Por cada gene:
    Atualiza valor de produto
    se quantidade de qualquer produto < 0 -> not feasible

- X Drone não pode levantar produtos de Customer nodes, apenas WH

Para cada gene
    Ver Node e determinar se é WH ou Customer
    Ver Demand
    Se Demand não corresponder ao tipo -> not feasible

- X Nenhuma order recebe mais produto do que o previsto

Para cada node de customer
Verifica quantidaeds recebidas e atualiza o que ainda precisa de receber
Se valor ficar negativo (recebeu a mais) -> not-feasible

### Evaluation functions

Cada order pode ter entre 1 e 100 pontos. Tendo n orders, o máximo total possível de pontos é 100*n. De acordo com o enunciado, a order fica completa quando o último item é entregue

Somatório da pontuação de todas as orders / 100*n -> [0,1]

Q: Como determinar se uma encomenda foi concluida?

A: Verificar se todos os genes de uma certa encomenda contêm drones associados, se sim, então foi realizada, já que obedece às restrições.

Q: Como determinar ultimo turn de uma encomenda?

A: Ver os genes de cada drone e criar uma lista de pares Ação-IntervaloDeTurnos, com as seguintes ações:
- PickUp
- Andamento + 1 - PA
- Deliver
- Andamento + 1 - DA

Exemplo Drone1:
PA - 1-6 (5 de andamento + 1 pickup)
PA - 7 (pickup apenas)
PE - 8-12 (4 de andamento + 1 delivery)
PE - 13 (apenas delivery)

## 4) Trabalho feito até agora

Parsing