Vehicle Routing Problem Algorithm in Functional JS
We already have Google Maps and even the GPT-4 is coming, then why bother thinking of hard problems like Vehicle Routing Problem (VRP)? Some might be motivated by business opportunities like some professional operation management softwares, earning millions through sales of API that solves their VRP problems. Me? I just do it for fun, and VRP is surely as tough — if not tougher — as everyone claims. Not being contend with achieving Directed Graph Pathfinding Algorithm in JS as posted before, I thirst for more challenges and VRP is right on the next track of what’s achieved before.
So in order to learn what VRP actually is, let’s dive into various sources we can find. When you type VRP on YouTube, you’ll mostly find relatively short videos that explain so little about the problem itself and try selling you their solutions instead, that’s why I prefer learning something from books or articles that discuss the problem in depth. One of the most approachable source is Wikipedia where at a section it states that VRP actually has many variants depends on what resource you have, the shape of the map, and what you’re trying to achive. While most problems deals with minimization of cost or distance, some are trying to maximize the profit. There are those that require the the vehicle to return while the other don’t. Some are satisfied with one vehicle trip, while the rest require the dispersion of multiple vehicles at once. It seems like the VRP is not a single problem, but a family of problems where a branch can sprout anytime following what’s required in the field.
I don’t aim to craft a solution that can satisfy all of them at once, as I may not have the brain capacity to build such thing, or sole perfect solution may not exists at all. If I may define the VRP problem myself, it’s all about minimizing cost of transportation — or satisfying certain conditions — given that there’re several destination for one trip. In prior article, I wrote a function which when given a graph, initial position, target destination, it shall yield all the possible routes available to be chosen. Perhaps I’d like to face this problem in the same manner. A VRP function which when given a graph of map, initial position, and a set of destinations, then it’ll yield all the possible routes to be chosen by the user later. Why not immediately yield the shortest route? Well, because not everyone would like the shortest route, do you expect an Ice Cream truck would choose the shortest route to somewhere while neglecting the other areas where the children craving for ice cream? So, let’s define the function requirement here:
- The function should accept a graph of a map, initial position, and a set of destinations (arbitrarily ordered)
- The function should take advantage of
pFinderfunction posted in prior article - The function should yield all the possible routes that crosses all given destination at once regardless of their order
- Functional paradigm is optional but strongly suggested for the sake of purity and simplicity
Now the constraints were defined and let’s see what we have up in our sleeves to craft the desired function. Let me show you a graph to help us visualize what we’re dealing with:
largeMap = {
a: {b: 8, c: 3, f: 13},
b: {d: 1, c: 2},
c: {b: 3, d: 9, e: 2},
d: {e: 4, h: 2, g: 6},
e: {i: 4, f: 5, a: 5},
f: {i: 7, g: 1},
g: {e: 3, h: 4},
h: {i: 1},
i: {g: 5}
}
pFinder(largeMap, 'a', 'd') /* gets [
{a: 8, b: 2, c: 9},
{a: 8, b: 1},
{a: 3, c: 3, b: 1},
{a: 3, c: 9}
] works pretty well */Now that’s a proper map worthy of representing this VRP problem. The little circles represents unique cities while the directional arrows represents the allowed path from a city to another. There’s obviously more edges than the vertices in this map. The nodes name should be in string format, or the function will unexpectedly misbehave. Let’s say we’re at city F and ought to deliver our goods to city C, D, and H. Shall we go CDH, DHC, HDC, HCD or what? We can’t be sure that each of those combinations would be valid for there are unreachable paths due to some of them edges are one way only.
I can’t embarrass myself by telling you the time gap it took from paragraph above to this one. “Maximum call stack exceeded” has been part of me now, and after uncountable amount of trial and errors, the snippets below is the best I can come up with:
withAs = (obj, cb) => cb(obj)
lastNode = paths => Object.keys(
paths.slice(-1)[0] || {}
).slice(-1)[0]
subset = (sub, set) => sub.length && set.length &&
sub.reduce((a, b) => a && set.includes(b), true)
solveVRP =
(algo, graph, from, places, trace = places, paths = []) =>
!trace.length || subset(places, Object.keys(paths.reduce(
(a, b) => ({...a, ...b}), {}
))) ? paths.map(JSON.stringify).join(';') :
trace.reduce((acc, dest) => [...acc, solveVRP(
algo, graph, lastNode(paths), places,
trace.filter(i => i !== dest), [...paths, withAs(
algo(graph, lastNode(paths) || from, dest),
short => short && ({...short, [dest]: 0})
)]
)], []).flat(1)
solveVRP(shortestPath, largeMap, 'a', ['d', 'f'])/* got these [
"{a:3,c:3,b:1,d:0};{d:4,e:5,f:0}",
"{a:3,c:2,e:5,f:0};"
] rather cryptic */
solveVRP is a function which when given certain pathfinding algorithm, a directed graph, initial position and a set of destinations then it shall yield an array of object-like strings that represents a path of combinatoric set of given destinations. The main idea is to trace a path from initial position to all given destinations, if the path managed to reach all the destinations at one go, then accumulate that path to an array, or skip if it doesn’t. The function calls itself by passing what’s been traced and shift the initial position to the next step, until all given destination becomes the subset of the traced path. Notice that you can pass either shortestPath or longestPath function mentioned before to give desired results. solveVRP itself doesn’t yield a pretty result, that’s why I need to create another function to make the results more appealing:
uniqObj = arrObj =>
[...new Set(arrObj.map(JSON.stringify) || {})]
.map(JSON.parse)
pathVRP = result => uniqObj(result.map(i => i.split(';').flatMap(
j => withAs(JSON.parse(j), obj => Object.keys(obj))
.map(k => [k, JSON.parse(j)[k]])
).filter((j, jx, arr) => jx === arr.length - 1 ? j : j[1])))
pathVRP(solveVRP(shortestPath, largeMap, 'a', ['g', 'h', 'i']))
/* gets 3 results, the shortests for each combinations
[['a', 3], ['c', 2], ['e', 5], ['f', 1], ['g', 4], ['h', 1], ['i', 0]], // GHI
[['a', 3], ['c', 3], ['b', 1], ['d', 2], ['h', 1], ['i', 5], ['g', 0]], // HIG
[['a', 3], ['c', 2], ['e', 4], ['i', 5], ['g', 4], ['h', 0]] // IGH
*/
Now the result is more properly represented where the array contains all possible paths from initial position to combined destinations at one go including its respective distance. You may examine the results by visually observing the map and confirm it. You may alter the solveVRP function to use longestPath or conditionPath if you so choose just to show you that it’s entirely possible. That’s why we gonna make more of it like the ones below.
Additional Functions
In previous article we went great length to extend the functionality of pFinder function to not only find the shortest path, but also the longest one, and the conditional one. Let’s be fair and give solveVRP the same treatment:
shortestVRP = (graph, from, destinations) =>
pathVRP(solveVRP(shortestPath, graph, from, destinations))
.sort((a, b) => sub([
sum(a.map(i => i[1])),
sum(b.map(i => i[1]))
]))[0]
shortestVRP(largeMap, 'a', ['g', 'h', 'i'])/* get these [
['a', 3], ['c', 3], ['b', 1],
['d', 2], ['h', 1], ['i', 5], ['g', 0],
] with total 15 points of distance */
longestVRP = (graph, from, destinations) =>
pathVRP(solveVRP(longestPath, graph, from, destinations))
.sort((a, b) => sub([
sum(b.map(i => i[1])),
sum(a.map(i => i[1]))
]))[0]
longestVRP(largeMap, 'a', ['g', 'h', 'i']) /* get these [
['a', 8], ['b', 2], ['c', 9], ['d', 4], ['e', 5],
['f', 7], ['i', 5], ['g', 4], ['h', 1], ['i', 0]
] with total 45 points of distance */
There you go, presented by both shortestVRP and longestVRP for any occasions. The conditionVRP momentarily doesn’t exists as the conditionPath function itself yields an array of paths rather than single path like the two before. Okay then, what’s next? I don’t know, have no idea. Feel free to give me new problems, I’d like to face them all with functional paradigm of Javascript.
Codes Recap
You can copy the entire snippet below to your browser console and hit Enter, then all the functions should be available for executions.
// From previous article
pFinder = (graph, from, dest, path = {[from]: 1}) =>
Object.keys(graph).filter(step => !path[step]).reduce(
(acc, next) => graph[from]?.[next] ? [...acc, ...pFinder(
graph, next, dest, {...path, [from]: graph[from][next]}
)] : [...acc, ...(!acc.length && from === dest ? [path] : [])], []
)
between = (low, mid, high) => low < mid && mid < high
sum = arr => arr.reduce((a, b) => a + b)
sub = ([first, ...rest]) => first - sum(rest)
shortestPath = (graph, from, dest) =>
pFinder(graph, from, dest).sort((a, b) => sub([
sum(Object.values(a)), sum(Object.values(b))
]))[0]
longestPath = (graph, from, dest) =>
pFinder(graph, from, dest).sort((a, b) => sub([
sum(Object.values(b)), sum(Object.values(a))
]))[0]
conditionPath = (graph, from, dest, cond) =>
pFinder(graph, from, dest).filter(cond)
// From current article
withAs = (obj, cb) => cb(obj)
uniqObj = arrObj =>
[...new Set(arrObj.map(JSON.stringify) || {})]
.map(JSON.parse)
lastNode = paths => Object.keys(
paths.slice(-1)[0] || {}
).slice(-1)[0]
subset = (sub, set) => sub.length && set.length &&
sub.reduce((a, b) => a && set.includes(b), true)
solveVRP =
(algo, graph, from, places, trace = places, paths = []) =>
!trace.length || subset(places, Object.keys(paths.reduce(
(a, b) => ({...a, ...b}), {}
))) ? paths.map(JSON.stringify).join(';') :
trace.reduce((acc, dest) => [...acc, solveVRP(
algo, graph, lastNode(paths), places,
trace.filter(i => i !== dest), [...paths, withAs(
algo(graph, lastNode(paths) || from, dest),
short => short && ({...short, [dest]: 0})
)]
)], []).flat(1)
pathVRP = result => uniqObj(result.map(i => i.split(';').flatMap(
j => withAs(JSON.parse(j), obj => Object.keys(obj))
.map(k => [k, JSON.parse(j)[k]])
).filter((j, jx, arr) => jx === arr.length - 1 ? j : j[1])))
shortestVRP = (graph, from, destinations) =>
pathVRP(solveVRP(shortestPath, graph, from, destinations))
.sort((a, b) => sub([
sum(a.map(i => i[1])),
sum(b.map(i => i[1]))
]))[0]
longestVRP = (graph, from, destinations) =>
pathVRP(solveVRP(longestPath, graph, from, destinations))
.sort((a, b) => sub([
sum(b.map(i => i[1])),
sum(a.map(i => i[1]))
]))[0]
