How to convert vehicle schedule time window calculation algorithm to FP

Question

I am working on an algorithm that optimizes utilitization of a vehicle. What I have is a list of paths the vehicle is planned to take and between which times (time windows) it has to be at a certain location.

I can also calculate the time it takes to get from one location to the next, but I have to take into account that the speed is not fixed - the driver can drive faster or slower between the points.

Let's say Vehicle1 has to take customer from A between 10am and 12am to B before 3pm. If I add another customer that has to go from C between 11am and 12am to D before 1pm. The time windows could change.

The durations at normal speed are A <- 10 min -> C <- 1h -> D <- 1.5h -> B. The driver can go .1x slower or faster (so from A-C he takes 10 * 1.1 = 11min if driving slowly and 10 * 0.9 = 9min if driving fast).

To calculate this iteratively I first make a pass forward to increase the driving window as much as possible and then reduce the window by making an intersection with the passenger windows. Then I make a pass going backwards, increasing the driving window again and making the intersection with the passenger windows and the previous window.

Here is the pseudo code:

for i=1 to locations.size:
  previous = locations[i-1]
  current = locations[i]
  duration = calculateDuration(previous, current)
  drivingWindow = previous.window.postpone(fast(duration), slow(duration))
  actualWindow = intersectWithPassengers(drivingWindow, passengers)
  current.window = actualWindow

for i=locations.size-2 to including 0:
  next = locations[i+1]
  current = locations[i]
  duration = calculateDuration(current, next)
  drivingWindow = next.window.prepone(slow(duration), fast(duration))
  intersectedWithPassengers = intersectWithPassengers(drivingWindow, passengers)
  current.window = current.window.intersection(intersectedWithPassengers)

Meaning of different functions and methods:

calculateDuration is probably clear
window.postpone(x, y) returns new window [a+x, b+y]
window.prepone(x, y) returns new window [a-x, b-y]
intersectWithPassengers is probably clear

If any of the windows don't intersect that means that the new passenger cannot be picked up. This algorithm keeps the windows as big as they can be, so more passengers can be picked up by the vehicle.

Algorithm goes as follows:

0. A[10, 12], C[11, 12], D[, 13], B[, 15] // what we start with
1. A[10, 12], C[11, 12], D[, 13], B[, 15] // driving: [10:09, 12:11], passengers: [11, 12]
2. A[10, 12], C[11, 12], D[11:54, 13], B[, 15] // driving: [11:54, 13:06], passengers: [, 13]
3. A[10, 12], C[11, 12], D[11:54, 13], B[13:15, 14:39] // driving: [13:15, 14:39], passengers: [, 15]

---

4. A[10, 12], C[11, 12], D[11:54, 13], B[13:15, 14:39] // driving: [11:36, 13:18], passengers: [, 13], current: [11:54, 13]
5. A[10, 12], C[11, 12], D[11:54, 13], B[13:15, 14:39] // driving: [10:48, 12:06], passengers: [11, 12], current: [11, 12]
6. A[10:49, 11:51], C[11, 12], D[11:54, 13], B[13:15, 14:39] // driving: [10:49, 11:51], passengers: [10, 12], current: [10, 12]

While this algorithm works, and it is optimal, the code seems ugly to me and not really clear what it does and why, but I cannot seem to find a cleaner way to do it. How would you approach this if you were doing FP or something close to FP?

Answer 1

I later analyzed this problem more and this is what I came up with:

X0 = PW0

Xi = (Xi-1 + [Fi-1, Si-1]) | PWi

Yn = Xn = Xn-1 + [Fn-1, Sn-1] | PWn

• Yi = (Yi+1 - [Si, Fi]) | PWi | Xi
• Yi = (Yi+1 - [Si, Fi]) | PWi | (Xi-1 + [Fi-1, Si-1]) | PWi

Yi = (Yi+1 - [Si, Fi]) | Xi

• X0 is starting window
• PW0 is first passenger window
• Xi is i-th window
• Fi duration at fast speed from location i to i+1
• Si duration at slow speed from location i to i+1
• | means intersection
• n number of locations
• Yi is the i-th window

Turns out that there is no need to calculate passenger intersections each time, because it is already captured in the first loop. It also turns out that passenger windows and durations can be precalculated, because they are constant.

Taking the equations into account, the code would look something like this:

const context = {
  PW, 
  F, 
  S,
}

function X(context, i) {
  if(i == 0) return context.PW[i]

  return X(context, i - 1).postpone(context.F[i - 1], context.S[i - 1])
         .intersect(context.PW[i])
}

function Y(context, i) {
  if(i == context.PW.length - 1) 
     return X(context, i)

  return Y(context, i + 1).prepone(context.S[i], context.F[i])
         .intersect(X(context, i))
}

function calculateWindows(context) {
  return range(context.PW.length).map(i => Y(context, i))
}

which is kind of insane in a good and a bad way.

Some more explanation:

When first looking at this problem what we are looking at first is:

• [StartFirst, EndFirst] = calculatePW(...)

And we can define every next window as previous window postponed by fast duration for start and slow duration for end, so that way we maximize the window, but we have to intersect it with all the passenger windows at that station

• [Start, End] = [StartPrev, EndPrev] + [fast(DfromPrevious), slow(DfromPrevious)] | PWsAtStation(...)
• [Si, Ei] = [Si-1, Ei-1] + [fast(Di-1), slow(Di-1)] | PWi_s(...)

We can take windows as a sort of vector, so we can do:

• Xi = Xi-1 + [fast(Di-1), slow(Di-1)] | PWi_s(...)

But passenger windows, fast durations and slow durations are always the same so we can precalculate them:

• Xi = (Xi-1 + [Fi-1, Si-1]) | PWi

This gives us the maximum possible windows that we can make if we pick up these passengers at the specified times. But we also have to go reverse to correct the possible mistakes that might have happened because some future window shrunk.

We start from the end window:

• Yn = Xn = Xn-1 + [Fn-1, Sn-1] | PWn

To maximize the starting window when we know the ending window, we have to subtract slow duration from the start of ending window and fast duration from the end of the ending window (basically do the opposite of what we did before).

• Yi = Yi+1 - [Si, Fi]

But we also have to take into account the passenger windows and previous driving window.

• Yi = (Yi+1 - [Si, Fi]) | PWi | Xi

And it turns out that taking passenger window into account again is unnecessary, giving us:

• Yi = (Yi+1 - [Si, Fi]) | Xi

I already turned the equations above into code, what is left is to just wire everything together. The main star of the show is TimeWindow class that takes care of the operations, everything else is there just to improve readability of the data.

const maxDate = new Date(8640000000000000);
const minDate = new Date(-8640000000000000);

function hs(date) {
    return date.toLocaleString("en-us", {hour: '2-digit', minute: '2-digit'})
}

class TimeWindow {
    constructor(start = minDate, end = maxDate) {
    this.start = start
    this.end = end
  }
  
  postpone(start, end) {
    return new TimeWindow(new Date(this.start.getTime() + start), new Date(this.end.getTime() + end))
  }
  
  prepone(start, end) {
    return new TimeWindow(new Date(this.start.getTime() - start), new Date(this.end.getTime() - end))
  }
  
  intersect(window) {
    const start = Math.max(this.start, window.start)
    const end = Math.min(this.end, window.end)
    
    return new TimeWindow(new Date(start), new Date(end))
  }
  
  toString() {
    return `[${hs(this.start)}, ${hs(this.end)}]`
  }
}

function friday(hour = 0, minute = 0) {
    return new Date(2021, 11, 10, hour, minute, 0)
}

function timeWindow(startTime, endTime) {
    const start = startTime ? friday(startTime[0], startTime[1]) : null
  const end = endTime ? friday(endTime[0], endTime[1]) : null
  
    return new TimeWindow(start, end)
}

function minutes(number) {
    return 1000 * 60 * number
}

function range(limit) {
    const result = []
  
  for(let i = 0; i < limit; i++) {
    result.push(i)
  }
  
  return result
}

We can now duplicate the inputs from the original post and run the function.

const PW = [
  timeWindow([10, 0], [12, 0]), 
  timeWindow([11, 0], [12, 0]),
  timeWindow(null, [13, 0]),
  timeWindow(null, [15, 0])
]
const D = [minutes(10), minutes(60), minutes(90)]
const F = D.map(i => i * 0.9)
const S = D.map(i => i * 1.2)

...

console.log(calculateWindows(context).map(window -> window.toString()))

Turns out I made a mistake in the original post. When calculating the last window I calculated slow duration as 99 minutes instead of 108 minutes (factor .1 instead of .2).

["[10:48, 11:51]", "[11:00, 12:00]", "[11:54, 13:00]", "[13:15, 14:48]"]

Here is the link to JsFiddle: https://jsfiddle.net/4s2c5j6y/20/

Answer 2

I haven't worked through the whole problem, but rewriting that first loop into something more functional seems pretty mechanical.

First, consider the outcome of that loop: an assignment into current.Window. Assignment isn't really functional. We should write a function that does the calculations that underlie that assignment.

Then, instead of writing some code later on that expects this loop to have already set current.Window, we can simply write a function that gets that value when it's needed. (This is a lot easier to reason about anyway. We shouldn't have to write code that assumes some other code did something at some difficult-to-nail-down appropriate time. That's murky, obsolete "object-oriented" thinking.)

I found it helpful to work from the bottom of the loop to its top. We have this at the bottom:

actualWindow = intersectWithPassengers(drivingWindow, passengers)
current.window = actualWindow

Thinking functionally, we might take this tiny step:

return intersectWithPassengers(drivingWindow, passengers)

That first parameter isn't functional, in that it's a stack variable that was assigned into. We can replace it with an expression from still farther up:

return intersectWithPassengers
    (previous.window.postpone(fast(duration), slow(duration)), passengers)

The "passengers" parameter is probably OK. I expect it can be a parameter to the function we're writing.

Calling fast and slow is OK (they're functions), but we can't pass in stack variables. We have to (again) pass in the appropriate expressions instead.

Following this replacement process its end, I obtained this:

 function getCurrentWindow (passengers, locations, i) 
     return intersectWithPassengers(
      (locations[i-1]).window.postpone(
       fast(calculateDuration(locations[i-1], locations[i])), 
       slow(calculateDuration(locations[i-1], locations[i]))), passengers)

Of course, you have to retool the other code to use a function instead of assuming some other code did some thing, but that's good. That's the whole point.