mapbox / mapbox/node-or-tools

Problem when providing pair of pickup and delivery indices

Open
#63 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
155
Forks
47
PR merge metrics
No merged PRs in 30d

Description

Hey,

There is this issue where providing a pair of pickup and delivery indices would lead to this error message: `Unable to find a solution`

## Expected Behavior
It should return a valid route order based on cost array.

## Current Behavior
Returns `Unable to find a solution`

## Steps to Reproduce
1. Copy `node-or-tools/test/vrp.js` file content to a new file
2. Remove all assertions
3. Add a pair of pickup and delivery indices in `searchOpts`.
```js
pickups: [4, 7],
deliveries: [7, 10]
```

## Context (Environment)
I have a pair of pickup and delivery indices and I want to visit one or more stops before visiting others.

This is my code snippet. You could see that if we remove the pickup and delivery indices, the code will work but after adding aforementioned indices, it returns `Unable to find a solution`

```js
module.exports = () => {
const ortools = require('node_or_tools')
var locations = [
[0, 0], [0, 1], [0, 2], [0, 3],
[1, 0], [1, 1], [1, 2], [1, 3],
[2, 0], [2, 1], [2, 2], [2, 3],
[3, 0], [3, 1], [3, 2], [3, 3]]

var depot = 0

function manhattanDistance(lhs, rhs) {
return Math.abs(lhs[0] - rhs[0]) + Math.abs(lhs[1] - rhs[1])
}

var costMatrix = new Array(locations.length)

for (var from = 0; from < locations.length; ++from) {
costMatrix[from] = new Array(locations.length)

for (var to = 0; to < locations.length; ++to) {
costMatrix[from][to] = manhattanDistance(locations[from], locations[to])
}
}

var dayStarts = Hours(0)
var dayEnds = Hours(3)

var seed = 2147483650

function ParkMillerRNG(seed) {
var modulus = 2147483647
var multiplier = 48271
var increment = 0
var state = seed

return function() {
state = (multiplier * state + increment) % modulus
return state / modulus
}
}

var rand = ParkMillerRNG(seed)

function Seconds(v) {
return v
}

function Minutes(v) {
return Seconds(v * 60)
}

function Hours(v) {
return Minutes(v * 60)
}

var durationMatrix = new Array(locations.length)

for (var from = 0; from < locations.length; ++from) {
durationMatrix[from] = new Array(locations.length)

for (var to = 0; to < locations.length; ++to) {
var serviceTime = Minutes(3)
var travelTime = Minutes(costMatrix[from][to])

durationMatrix[from][to] = serviceTime + travelTime
}
}

var timeWindows = new Array(locations.length)

for (var at = 0; at < locations.length; ++at) {
if (at === depot) {
timeWindows[at] = [dayStarts, dayEnds]
continue
}

var earliest = dayStarts
var latest = dayEnds - Hours(1)

var start = rand() * (latest - earliest) + earliest
var stop = rand() * (latest - start) + start

timeWindows[at] = [start, stop]
}

var demandMatrix = new Array(locations.length)

for (var from = 0; from < locations.length; ++from) {
demandMatrix[from] = new Array(locations.length)

for (var to = 0; to < locations.length; ++to) {
if (from === depot)
demandMatrix[from][to] = 0
else
demandMatrix[from][to] = 1
}
}

var solverOpts = {
numNodes: locations.length,
costs: costMatrix,
durations: durationMatrix,
timeWindows: timeWindows,
demands: demandMatrix
}

var VRP = new ortools.VRP(solverOpts)

var numVehicles = 10
var timeHorizon = dayEnds - dayStarts
var vehicleCapacity = 10

// Dummy lock to let vehicle 0 go to location 2 and 3 first - to test route locks
var routeLocks = new Array(numVehicles)

for (var vehicle = 0; vehicle < numVehicles; ++vehicle) {
if (vehicle === 0)
routeLocks[vehicle] = [2, 3]
else
routeLocks[vehicle] = []
}

var searchOpts = {
computeTimeLimit: 1000,
numVehicles: numVehicles,
depotNode: depot,
timeHorizon: timeHorizon,
vehicleCapacity: vehicleCapacity,
routeLocks: routeLocks,
pickups: [4, 7],
deliveries: [7, 10]
}

VRP.Solve(searchOpts, function(err, solution) {

console.log('**********************')
console.log(err,solution)
console.log('**********************')
function used(v) {
return v.length == 0 ? 0 : 1
}

function addition(l, r) {
return l + r
}

var numVehiclesUsed = solution.routes.map(used).reduce(addition, 0)

function checkRoute(v) {
var depotInRoute = v.find(function(u) {
return u == depot
})
}

function checkTimeWindows(v) {
v.forEach(function(u) {
})
}

solution.routes.forEach(checkRoute)
solution.times.forEach(checkTimeWindows)

})

}

```

Contributor guide

Open the contributing guide

Research direction

Start with node-or-tools/test/vrp.js, reproduce the failure using the shown pickups, deliveries, routeLocks, and time windows, and trace the VRP.Solve entry point into the binding. Compare the failing case with the same example without pickup and delivery indices. Done means the example returns a valid route order without reporting "Unable to find a solution".

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp, javascript, node.js
Domain
backend
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.