reinterpretcat / vrp

A Vehicle Routing Problem solver
https://reinterpretcat.github.io/vrp/
Apache License 2.0
331 stars 68 forks source link

multiple areas #75

Open tdeenes opened 2 years ago

tdeenes commented 2 years ago

@reinterpretcat The recent area-order feature is very useful. Would it be possible to support multiple areas per vehicle?. I tried to use

        "limits": {
          "areas": [
            [
              {
                "areaId": "A",
                "jobValue": 4
              },
              {
                "areaId": "B",
                "jobValue": 1
              }
            ]
          ]
        }

or

        "limits": {
          "areas": [
            [
              {
                "areaId": "A",
                "jobValue": 4
              }
            ],
            [
              {
                "areaId": "B",
                "jobValue": 1
              }
            ]
          ]
        }

I receive no error message but those limits are ignored.

Full example:

{
  "plan": {
    "areas": [
      {
        "id": "A",
        "jobs": [
          "job4",
          "job10",
          "job1"
        ]
      },
      {
        "id": "B",
        "jobs": [
          "job8",
          "job5",
          "job3"
        ]
      }
    ],
    "jobs": [
      {
        "id": "job1",
        "deliveries": [
          {
            "places": [
              {
                "location": {
                  "lat": 52.59241,
                  "lng": 13.50974
                },
                "duration": 300.0
              }
            ],
            "demand": [
              1
            ]
          }
        ]
      },
      {
        "id": "job2",
        "deliveries": [
          {
            "places": [
              {
                "location": {
                  "lat": 52.61066,
                  "lng": 13.45378
                },
                "duration": 300.0
              }
            ],
            "demand": [
              1
            ]
          }
        ]
      },
      {
        "id": "job3",
        "deliveries": [
          {
            "places": [
              {
                "location": {
                  "lat": 52.36284,
                  "lng": 13.68558
                },
                "duration": 300.0
              }
            ],
            "demand": [
              1
            ]
          }
        ]
      },
      {
        "id": "job4",
        "deliveries": [
          {
            "places": [
              {
                "location": {
                  "lat": 52.35415,
                  "lng": 13.19889
                },
                "duration": 300.0
              }
            ],
            "demand": [
              1
            ]
          }
        ]
      },
      {
        "id": "job5",
        "deliveries": [
          {
            "places": [
              {
                "location": {
                  "lat": 52.47351,
                  "lng": 13.52510
                },
                "duration": 300.0
              }
            ],
            "demand": [
              1
            ]
          }
        ]
      },
      {
        "id": "job6",
        "deliveries": [
          {
            "places": [
              {
                "location": {
                  "lat": 52.63608,
                  "lng": 13.38014
                },
                "duration": 300.0
              }
            ],
            "demand": [
              1
            ]
          }
        ]
      },
      {
        "id": "job7",
        "deliveries": [
          {
            "places": [
              {
                "location": {
                  "lat": 52.67531,
                  "lng": 13.26834
                },
                "duration": 300.0
              }
            ],
            "demand": [
              1
            ]
          }
        ]
      },
      {
        "id": "job8",
        "deliveries": [
          {
            "places": [
              {
                "location": {
                  "lat": 52.68782,
                  "lng": 13.39262
                },
                "duration": 300.0
              }
            ],
            "demand": [
              1
            ]
          }
        ]
      },
      {
        "id": "job9",
        "deliveries": [
          {
            "places": [
              {
                "location": {
                  "lat": 52.45387,
                  "lng": 13.53358
                },
                "duration": 300.0
              }
            ],
            "demand": [
              1
            ]
          }
        ]
      },
      {
        "id": "job10",
        "deliveries": [
          {
            "places": [
              {
                "location": {
                  "lat": 52.51858,
                  "lng": 13.28350
                },
                "duration": 300.0
              }
            ],
            "demand": [
              1
            ]
          }
        ]
      }
    ]
  },
  "fleet": {
    "vehicles": [
      {
        "typeId": "type1",
        "vehicleIds": [
          "vehicle_11", "vehicle_12"
        ],
        "profile": {
          "matrix": "car"
        },
        "costs": {
          "fixed": 25.0,
          "distance": 0.0002,
          "time": 0.005
        },
        "shifts": [
          {
            "start": {
              "earliest": "2020-05-01T09:00:00.00Z",
              "location": {
                "lat": 52.4181,
                "lng": 13.4637
              }
            },
            "end": {
              "latest": "2020-05-01T19:00:00.00Z",
              "location": {
                "lat": 52.4181,
                "lng": 13.4637
              }
            },
            "reloads": [
              {
                "location": {
                  "lat": 52.4181,
                  "lng": 13.4637
                },
                "duration": 0
              }
            ]
          }
        ],
        "capacity": [
          5
        ],
        "limits": {
          "areas": [
            [
              {
                "areaId": "A",
                "jobValue": 4
              },
              {
                "areaId": "B",
                "jobValue": 1
              }
            ]
          ]
        }
      },
      {
        "typeId": "type2",
        "vehicleIds": [
          "vehicle_21", "vehicle_22"
        ],
        "profile": {
          "matrix": "car"
        },
        "costs": {
          "fixed": 25.0,
          "distance": 0.0002,
          "time": 0.005
        },
        "shifts": [
          {
            "start": {
              "earliest": "2020-05-01T09:00:00.00Z",
              "location": {
                "lat": 52.4181,
                "lng": 13.4637
              }
            },
            "end": {
              "latest": "2020-05-01T19:00:00.00Z",
              "location": {
                "lat": 52.4181,
                "lng": 13.4637
              }
            },
            "reloads": [
              {
                "location": {
                  "lat": 52.4181,
                  "lng": 13.4637
                },
                "duration": 0
              }
            ]
          }
        ],
        "capacity": [
          5
        ],
        "limits": {
          "areas": [
            [
              {
                "areaId": "B",
                "jobValue": 3
              }
            ]
          ]
        }
      }
    ],
    "profiles": [
      {
        "name": "car",
        "type": "car"
      }
    ]
  },
  "objectives": [
    [
      {
        "type": "minimize-unassigned"
      }
    ],
    [
      {
        "type": "minimize-tours"
      },
      {
        "type": "area-order",
        "isConstrained": false,
        "isValuePreferred": true
      }
    ],
    [
      {
        "type": "minimize-cost"
      }
    ]
  ]
}
tdeenes commented 2 years ago

I would expect for the example above that 'type1' vehicle is used, but the solution picks 'type2'.

reinterpretcat commented 2 years ago

It is a bit experimental feature, but have you tried to set "isConstrained": true for the area-order objective?

tdeenes commented 2 years ago

yup, same result