-1

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:

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

  1. 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]
  2. 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]
  3. 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?

2
  • There's a couple small jumps of logic from your question that I don't completely understand. You go from "I have an optimal algorithm that works" (Good!) to "It's ugly" (Why?) to "How would you do it in FP" (Why?). Is there any issue with your algorithm beside the fact that it is supposedly ugly and not FP? Dec 1 '21 at 21:32
  • Ugly: because of for loops and querying that happens in them... It just doesn't feel right for what it does. Can't put a finger on it, but just a feeling. Why do it in FP? Because. I'm not planning to change it unless FP is somehow much cleaner, but I'm just interested how this could be done in FP. The problem I come to is, that windows are related to each other, and are not immutable (the change of the current window is going to collide with the change of the next window). I don't know much of FP, only the principles and this problem seems to be hard to solve with it (at least for me).
    – Blaž Mrak
    Dec 1 '21 at 21:41
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/

5
  • i love this answer but am hesitant to upvote without unit tests :)
    – Ewan
    Dec 10 '21 at 11:31
  • Well, I have mathematically proven it and just put it into code. I could explain deeper how I came up with the formulas, but I essentially just turned my for loops into formulas and removed duplication :)
    – Blaž Mrak
    Dec 10 '21 at 11:51
  • @Ewan I will update the answer with actual implementation and tests as well and explain the math better.
    – Blaž Mrak
    Dec 10 '21 at 12:09
  • yeah that why i like your answer, the problem is, are you wrong? I would have to do the leg work!
    – Ewan
    Dec 10 '21 at 16:55
  • 1
    @Ewan here is the code with the added explanation. Turns out I wasn't wrong :D
    – Blaž Mrak
    Dec 10 '21 at 16:59
-1

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.

8
  • This is not helpful, because first: it doesn't tackle the main issue I have - How to avoid mutating the windows of locations (current window is dependent on what the previous window has become) and second: just because you don't use temporary variables, doesn't make your code functional and third: because you don't use temporary variables the code is close to unreadable and unclear about what it does.
    – Blaž Mrak
    Dec 10 '21 at 4:15
  • The code at the bottom of my example is a pure function. It doesn't get any more "functional" than that. And the techniques I used should be mostly sufficient for the conversion process. You might need to add recursion. Just keep doing what I did, from the inside of the code out. As for "the main issue you have," consider that you don't have to mutate anything. You can write a function that accepts your "locations" collection and returns a completely new collection based on it. And "unclear?" read what I said about depending on some "other code" to set things up for you. This way is better. Dec 10 '21 at 4:29
  • Also, reading your question and your comment, I think you're getting hung up on readability and looking at FP as some answer to that problem. It's not. While I won't stereotype functional code as "write-only code" (though that is something I've heard said about LISP), there's certainly nothing inherently "easier to read" about functional code. Easier to analyze in complex systems? Easier to parallelize? "Yes" to both questions, but it's not some cure-all for legibility. Nothing really is. Dec 10 '21 at 4:45
  • what do you mean by depending on some other code? You are missing the point. What you did is exactly the same as what I did in the loop, just much more tangled up and instead of looking at meaningful names, you are looking at locations[i] and locations[i-1]. That is not the fault of functional style and there is exactly 0 benefit from it. You turned x = calc(y); return x + 3; into return calc(y) + 3;. This isn't helpful, I know that variables can be replaced with the same function call and this is not what the question was about.
    – Blaž Mrak
    Dec 10 '21 at 5:01
  • 1
    "If your language allows it"- you'd have to be a real functional purist to make a language that doesn't. There's a language called simply "FP" where it's a true statement. Most LISPs provide some facility for variables (sometimes beyond just stack variables), though they do tend to cordon them off using syntax that kind of asks, "are you sure you need this?". I'm thinking of things like "set!" in Clojure and Scheme, which is a bit more typing than := or = would be in a less-FP-oriented language. Jan 7 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.