Dealing with right left side pickup issues

Overview

When picking up containers in the trash collection problem as well as other more abstract problems like passenger up pick or drop off, we might want to say that a passenger, package or container can only be picked up from the side of the street that it is located on. This was not originally possible because we did not have enough information available to make this assessment. Resent changes to the code that involve selecting containers along a path allow us to evaluate whether the container is to the right or left of the direction of travel along the path and potentially allow us to solve this problem in future code but it is not without some problems that need to be overcome.

Problems

• We have a path, ie: an order set of coordinates in the direction of travel from point A to B, but we do not know if a street on the path is one way or two way.
• If a container is on the left side of a one way street then we can never pick it up because it could only be picked up by driving the wrong way down the one way street.
• We need to define how this will impact data loading and how/when to trigger this behavior in the code

Implementation

Node::positionAlongSegment, which is called from twc::getNodesOnPath, is used to determine if the node is close to the path. The math for this that you have a path segment, and a container node, we drop a normal onto the segment. A simple cross product will determine if the container is on the left or right, length of (NC) tells us if its on the segment. So this could be modified to only return the container if it is to the right or on the segment.

      E
     /
    /
   N
  /    C
 /
S

Segment (SE)
Container C
projection of C onto (SE) is N

if length((NC)) == 0.0 then C is on the (SE)
if Z((NC) cross (SE)) < 0 then left side else right side

https://github.com/woodbri/vehicle-routing-problems/blob/release-v5/src/baseClasses/node.cpp#L214

One way streets

One way streets are a little harder to deal with because we to not have the actual street information as OSRM is doing the routing and we only have a directional path. One way to solve this would be to have the container say if it is on a one way street or not, or better yet, to say if it can be picked up only from the side it is located on or from either side.

• This will mean that the container table structure used to load the containers will need to change. We currently pass a street id field that is not getting used and is set to -1, and this could get re-purposed to pass the right-left-either side pickup flag
• the Node class will need to be changed to include this flag
• the data loader will need to pick up this value and set the new flag

When to activate this capability

There are multiple potential ways to activate this behavior. Some are:

• As an argument passed to the SQL vrp_trashcollection() function
• As part of the vehicle definition
  • this would require change the vehicle table definition
  • adding a flag to Vehicle class
  • making sure all Vehicle related code honors the new flag
  • and to make sure the flag is honored by lower level code like Node that does the computations
• Make it a compile time flag where it is always active or not.

Effort

I do not currently have an estimate of the time needed to do this and it will vary depending on some of the design decisions mentioned above. It will impact a lot of classes and therefore require a lot of testing to make sure that things do not break.