Hello @egerding, this is the logic for checking whether an insert into the current route is feasible. It can be briefly described as follows:
Verify adjacent tour nodes before inserting between them.
If either adjacent tour_nodes have the same location_id, reject the insertion.
Else if left_node is None, this means right_node is the head node. Accept insertion only if the new arrival time of right_node does not exceed its original departure time.
Else if right_node is None, left_node is the tail node. In this case, always accept the insertion since there are no nodes beyond left_node that will be affected.
Else if both left_node and right_node is not None, the insertion is accepted only if the the new arrival time of right_node after the insertion does not exceed its original departure time.
One of the reason for enforcing this criteria is that for each insert, the update to the current linked list of tour nodes only takes constant time. If we allow inserts without conditions, every tour nodes after the newly inserted tour node could be affected, meaning each insert would potentially require O(n) time complexity. This will be too costly.
Another reason is that by ensuring that the departure times of each tour node does not change, we are making sure that earlier passengers would have more advantage than later passengers.
https://github.com/MaxOng99/ECS-Ridesharing/blob/3ff9e16688a86dde56b803a732fe7a14b9325400/src/algorithms/greedy_insert.py#L275-L317
Hello @egerding, this is the logic for checking whether an insert into the current route is feasible. It can be briefly described as follows:
tour_nodeshave the samelocation_id, reject the insertion.left_nodeisNone, this meansright_nodeis the head node. Accept insertion only if the new arrival time ofright_nodedoes not exceed its original departure time.right_nodeisNone,left_nodeis the tail node. In this case, always accept the insertion since there are no nodes beyondleft_nodethat will be affected.left_nodeandright_nodeis notNone, the insertion is accepted only if the the new arrival time ofright_nodeafter the insertion does not exceed its original departure time.One of the reason for enforcing this criteria is that for each insert, the update to the current linked list of tour nodes only takes constant time. If we allow inserts without conditions, every tour nodes after the newly inserted tour node could be affected, meaning each insert would potentially require O(n) time complexity. This will be too costly.
Another reason is that by ensuring that the departure times of each tour node does not change, we are making sure that earlier passengers would have more advantage than later passengers.