search

VROOM-Project / vroom

Vehicle Routing Open-source Optimization Machine
http://vroom-project.org/
BSD 2-Clause "Simplified" License
1.35k stars 339 forks source link

I got obvious suboptimal result, please help to check. #564

Closed newforrestgump001 closed 3 years ago

newforrestgump001 commented 3 years ago

For one vehicle it is optimal. Steps for vehicle 0 (cost: 580 - duration: 580 - service: 0) Start - arrival: 0 - duration: 0 - service: 0 Job 0 - arrival: 0 - duration: 0 - service: 0 Job 17 - arrival: 34 - duration: 34 - service: 0 Job 16 - arrival: 68 - duration: 68 - service: 0 Job 15 - arrival: 102 - duration: 102 - service: 0 Job 14 - arrival: 136 - duration: 136 - service: 0 Job 13 - arrival: 170 - duration: 170 - service: 0 Job 12 - arrival: 205 - duration: 205 - service: 0 Job 11 - arrival: 239 - duration: 239 - service: 0 Job 10 - arrival: 273 - duration: 273 - service: 0 Job 9 - arrival: 307 - duration: 307 - service: 0 Job 8 - arrival: 341 - duration: 341 - service: 0 Job 7 - arrival: 375 - duration: 375 - service: 0 Job 6 - arrival: 409 - duration: 409 - service: 0 Job 5 - arrival: 443 - duration: 443 - service: 0 Job 4 - arrival: 477 - duration: 477 - service: 0 Job 3 - arrival: 512 - duration: 512 - service: 0 Job 2 - arrival: 546 - duration: 546 - service: 0 Job 1 - arrival: 580 - duration: 580 - service: 0 End - arrival: 580 - duration: 580 - service: 0

But for two vehicle, it is sub-optimal.

Start - arrival: 0 - duration: 0 - service: 0 Job 0 - arrival: 0 - duration: 0 - service: 0 Job 17 - arrival: 34 - duration: 34 - service: 0 Job 16 - arrival: 68 - duration: 68 - service: 0 Job 15 - arrival: 102 - duration: 102 - service: 0 Job 14 - arrival: 136 - duration: 136 - service: 0 Job 13 - arrival: 170 - duration: 170 - service: 0 Job 12 - arrival: 205 - duration: 205 - service: 0 Job 11 - arrival: 239 - duration: 239 - service: 0 Job 10 - arrival: 273 - duration: 273 - service: 0 Job 9 - arrival: 307 - duration: 307 - service: 0 Job 8 - arrival: 341 - duration: 341 - service: 0 Job 7 - arrival: 375 - duration: 375 - service: 0 Job 6 - arrival: 409 - duration: 409 - service: 0 Job 5 - arrival: 443 - duration: 443 - service: 0 Job 4 - arrival: 477 - duration: 477 - service: 0 End - arrival: 477 - duration: 477 - service: 0 Steps for vehicle 1 (cost: 68 - duration: 68 - service: 0) Start - arrival: 0 - duration: 0 - service: 0 Job 1 - arrival: 0 - duration: 0 - service: 0 Job 2 - arrival: 34 - duration: 34 - service: 0 Job 3 - arrival: 68 - duration: 68 - service: 0 End - arrival: 68 - duration: 68 - service: 0

The cost matrix: {0,34,68,99,128,152,172,187,195,199,195,187,172,152,128,99,68,34}, {34,0,34,67,99,127,151,171,186,194,198,195,186,171,152,127,99,68}, {68,34,0,34,68,99,126,152,171,186,195,198,195,186,172,152,128,99}, {99,67,34,0,35,68,99,127,152,172,186,195,198,195,186,172,152,127}, {128,99,68,35,0,34,67,99,127,151,171,186,195,198,196,186,172,152}, {152,127,99,68,34,0,34,68,99,127,152,172,186,196,198,195,186,171}, {172,151,126,99,67,34,0,34,68,99,127,152,172,186,195,197,195,185}, {187,171,152,127,99,68,34,0,34,68,99,128,152,172,186,195,198,195}, {195,186,171,152,127,99,68,34,0,34,68,99,127,152,171,185,195,198}, {199,194,186,172,151,127,99,68,34,0,34,68,98,127,151,171,186,194}, {195,198,195,186,171,152,127,99,68,34,0,34,67,99,127,151,171,186}, {187,195,198,195,186,172,152,128,99,68,34,0,34,68,99,126,152,171}, {172,186,195,198,195,186,172,152,127,98,67,34,0,35,68,99,127,152}, {152,171,186,195,198,196,186,172,152,127,99,68,35,0,34,67,99,127}, {128,152,172,186,196,198,195,186,171,151,127,99,68,34,0,34,68,99}, {99,127,152,172,186,195,197,195,185,171,151,126,99,67,34,0,34,68}, {68,99,128,152,172,186,195,198,195,186,171,152,127,99,68,34,0,34}, {34,68,99,127,152,171,185,195,198,194,186,171,152,127,99,68,34,0},

the 18 points forms a circle, and the distances between every two adjacent points are equal. //The code for the two vehicles. // Define vehicles (use std::nullopt for no start or no end). vroom::Location v_start1(0); // index in the provided matrix. vroom::Location v_start2(1); // index in the provided matrix. vroom::Vehicle v1(0, // id v_start1, // start std::nullopt); // not care end vroom::Vehicle v2(1, // id v_start2, // start std::nullopt); // not care end problem_instance.add_vehicle(v1); problem_instance.add_vehicle(v2);

Please help to check and sincere thanks!

jcoupey commented 3 years ago

Hard to tell what's going on without being able to reproduce, which is not easy based on a simple output description. Can you share the exact changes you made to the original example as a patch (result from running git diff libvroom_examples/libvroom.cpp).

the 18 points forms a circle

This does not show up easily through a matrix, it could help to share the locations too.

krypt-n commented 3 years ago

I think this works: https://gist.github.com/krypt-n/7e07418b1cfa875d9e55077c230bba23

However, I don't see how the solution is suboptimal. The distance between two adjacent jobs is 34 (or 35 in two cases). So a single vehicle starting at 0 takes 24 15 + 35 2 = 580 cost. If a second vehicle is used, vroom divides the jobs between them such that one of the 35 cost edges is not takes, resulting in a cost of 34 * 15 + 35 = 545.

What kind of solution do you expect?

newforrestgump001 commented 3 years ago

@krypt-n @jcoupey Sorry for late responce!

newforrestgump001 commented 3 years ago

This is my modified libvroom.cpp, please help to check it whether it is right or not when you are not busy, thank you!

newforrestgump001 commented 3 years ago

include

include

include "routing/osrm_routed_wrapper.h"

include "structures/vroom/input/input.h"

include "structures/vroom/job.h"

include "structures/vroom/vehicle.h"

include "utils/exception.h"

void log_solution(const vroom::Solution& sol, bool geometry) { std::cout << "Total cost: " << sol.summary.cost << std::endl; std::cout << "Unassigned: " << sol.summary.unassigned << std::endl;

// Log unassigned jobs if any. std::cout << "Unassigned job ids: "; for (const auto& j : sol.unassigned) { std::cout << j.id << ", "; } std::cout << std::endl;

// Describe routes in solution. for (const auto& route : sol.routes) { std::cout << "Steps for vehicle " << route.vehicle << " (cost: " << route.cost; std::cout << " - duration: " << route.duration; std::cout << " - service: " << route.service; if (geometry) { std::cout << " - distance: " << route.distance; }

std::cout << ")" << std::endl;

// Describe all route steps.
for (const auto& step : route.steps) {
  std::string type;
  switch (step.step_type) {
  case vroom::STEP_TYPE::START:
    type = "Start";
    break;
  case vroom::STEP_TYPE::END:
    type = "End";
    break;
  case vroom::STEP_TYPE::BREAK:
    type = "Break";
    break;
  case vroom::STEP_TYPE::JOB:
    switch (step.job_type) {
    case vroom::JOB_TYPE::SINGLE:
      type = "Job";
      break;
    case vroom::JOB_TYPE::PICKUP:
      type = "Pickup";
      break;
    case vroom::JOB_TYPE::DELIVERY:
      type = "Delivery";
      break;
    }
    break;
  }
  std::cout << type;

  // Add job/pickup/delivery/break ids.
  if (step.step_type != vroom::STEP_TYPE::START and
      step.step_type != vroom::STEP_TYPE::END) {
    std::cout << " " << step.id;
  }

  // Add location if known.
  if (step.location.has_coordinates()) {
    std::cout << " - " << step.location.lon() << ";" << step.location.lat();
  }

  std::cout << " - arrival: " << step.arrival;
  std::cout << " - duration: " << step.duration;
  std::cout << " - service: " << step.service;

  // Add extra step info if geometry is required.
  if (geometry) {
    std::cout << " - distance: " << step.distance;
  }
  std::cout << std::endl;
}

} }

struct point { int x; int y; };

void run_example_with_custom_matrix() { bool GEOMETRY = false; unsigned amount_dimension = 0; // No capacity constraint.

vroom::Input problem_instance(amount_dimension);

// Define custom matrix and bypass OSRM call. const int dim = 18; vroom::Matrix matrix_input(dim); int delta_theta = 20; int temp_r = 100; std::vector point_vec; std::vector<std::vector> time_matrix; time_matrix.resize(360 / delta_theta); for (auto&& item : time_matrix) { item.resize(360 / delta_theta); }

for (int i = 0; i < 360 / delta_theta; i++) { double theta_p = i delta_theta; double sin_theta = std::sin(theta_p 3.141592 / 180); double cos_theta = std::cos(theta_p 3.141592 / 180); int polar_x = (int)(temp_r cos_theta); int polar_y = (int)(temp_r * sin_theta); point_vec.push_back(point{polar_x, polar_y}); } for (int index_row = 0; index_row < point_vec.size(); index_row++) { for (int index_col = 0; index_col < point_vec.size(); index_col++) { time_matrix[index_row][index_col] = std::sqrt( std::pow((point_vec[index_row].x - point_vec[index_col].x), 2) + std::pow((point_vec[index_row].y - point_vec[index_col].y), 2)); } } for (int index_row = 0; index_row < dim; index_row++) { for (int index_col = 0; index_col < dim; index_col++) { matrix_input[index_row][index_col] = time_matrix[index_row][index_col]; } }

problem_instance.set_matrix("car", std::move(matrix_input));

// Define vehicles (use std::nullopt for no start or no end). vroom::Location v_start1(0); // index in the provided matrix. vroom::Location v_start2(1); // index in the provided matrix. vroom::Vehicle v1(0, // id v_start1, // start std::nullopt); // not care end vroom::Vehicle v2(1, // id v_start2, // start std::nullopt); // not care end problem_instance.add_vehicle(v1); problem_instance.add_vehicle(v2);

std::vector jobs; for (int index_row = 2; index_row < dim; index_row++) { jobs.push_back(vroom::Job(index_row, index_row)); }

for (const auto& j : jobs) { problem_instance.add_job(j); }

// Solve! auto sol = problem_instance.solve(5, // Exploration level. 4); // Use 4 threads.

log_solution(sol, GEOMETRY); }

int main() { try { run_example_with_custom_matrix(); } catch (const vroom::Exception& e) { std::cerr << "[Error] " << e.message << std::endl; } return 0; }

newforrestgump001 commented 3 years ago

The optimal result in my opinion is : I0906 10:44:12.639003 26194 tsp_simple_v20.cc:89] Route for vehicle 0: I0906 10:44:12.639081 26194 tsp_simple_v20.cc:99] 0 Time(0, 0) -> 1 Time(34, 34) -> 2 Time(68, 68) -> 3 Time(102, 102) -> 4 Time(137, 137) -> 5 Time(171, 171) -> 6 Time(205, 205) -> 7 Time(239, 239) -> 8 Time(273, 273) I0906 10:44:12.639089 26194 tsp_simple_v20.cc:101] Time of the route: 273min I0906 10:44:12.639094 26194 tsp_simple_v20.cc:89] Route for vehicle 1: I0906 10:44:12.639102 26194 tsp_simple_v20.cc:99] 0 Time(0, 0) -> 17 Time(34, 34) -> 16 Time(68, 68) -> 15 Time(102, 102) -> 14 Time(136, 136) -> 13 Time(170, 170) -> 12 Time(205, 205) -> 11 Time(239, 239) -> 10 Time(273, 273) -> 9 Time(307, 307)

newforrestgump001 commented 3 years ago

The first vehicle follows the upper semi-circle, and the second vehicle follows the lower semi-circle, Do you agree with me? Sorry for my poor English at the same time!

newforrestgump001 commented 3 years ago

I think this works: https://gist.github.com/krypt-n/7e07418b1cfa875d9e55077c230bba23

However, I don't see how the solution is suboptimal. The distance between two adjacent jobs is 34 (or 35 in two cases). So a single vehicle starting at 0 takes 24 15 + 35 2 = 580 cost. If a second vehicle is used, vroom divides the jobs between them such that one of the 35 cost edges is not takes, resulting in a cost of 34 * 15 + 35 = 545.

What kind of solution do you expect? I expect the balanced result between two vehicles, could you help me to get the result? I0906 10:44:12.639003 26194 tsp_simple_v20.cc:89] Route for vehicle 0: I0906 10:44:12.639081 26194 tsp_simple_v20.cc:99] 0 Time(0, 0) -> 1 Time(34, 34) -> 2 Time(68, 68) -> 3 Time(102, 102) -> 4 Time(137, 137) -> 5 Time(171, 171) -> 6 Time(205, 205) -> 7 Time(239, 239) -> 8 Time(273, 273) I0906 10:44:12.639089 26194 tsp_simple_v20.cc:101] Time of the route: 273min I0906 10:44:12.639094 26194 tsp_simple_v20.cc:89] Route for vehicle 1: I0906 10:44:12.639102 26194 tsp_simple_v20.cc:99] 0 Time(0, 0) -> 17 Time(34, 34) -> 16 Time(68, 68) -> 15 Time(102, 102) -> 14 Time(136, 136) -> 13 Time(170, 170) -> 12 Time(205, 205) -> 11 Time(239, 239) -> 10 Time(273, 273) -> 9 Time(307, 307)

jcoupey commented 3 years ago

@newforrestgump001 we're happy to take a look but you have to make it easier for us to help you since we have to do a lot of guesses here:

The optimal result in my opinion is :

If I trust the Time... part in your description, your own solution costs 273 + 307 = 580, I don't see how that's better than the 545 cost detailed above?

newforrestgump001 commented 3 years ago

Oh,sorry for ambiguous explanation. I want to get balanced result for two vehicles. for example Vehicle 0 time 273 ; Vehicle 1 time 307, then We can get the jobs done in shorter time. Sincere thanks for @jcoupey @krypt-n !

newforrestgump001 commented 3 years ago

I have checked the code,because of the github editor "<" ">" issue, the first two lines are incomplete, this is the reason you can not compile and link. So add the first two lines manually, so it will be okay.

include "<" iostream ">"

include "<" cmath ">"

Thanks again for kindly help!

jcoupey commented 3 years ago

Thanks for the clarification. The optimization objective is to reduce overall cost so what you're seeing is an expected behavior. If you badly need a solution using two vehicles, you can reach it by imposing any constraint that make the one-vehicle solution invalid. For example the new max_tasks key for vehicles would do the job. Other options include time window, capacity, skills... The relevant one depends on your use-case.

On the code formatting side, you may want to check the GitHub markdown syntax.

newforrestgump001 commented 3 years ago

@jcoupey Thank you a lot! Actually I want get the min( time every vehicle costs) as the objective. And the max_tasks of each vehicle is not fixed, for example, it may be 200 or 2000. I want to get the jobs(of all vechiles) done as soon as possible.
This is the code sample for or-tools of google. Does vroom has the feature? Thanks! std::string time{"Time"}; routing.AddDimension(transit_callback_index, // transit callback index int64{1000000}, // allow waiting time int64{1000000}, // maximum time per vehicle true, // Don't force start cumul to zero time); const RoutingDimension &time_dimension = routing.GetDimensionOrDie(time); routing.GetMutableDimension("Time")->SetGlobalSpanCostCoefficient(1);

jcoupey commented 3 years ago

I want to get the jobs(of all vechiles) done as soon as possible

Then that is not possible out-of-the-box, see #466.

newforrestgump001 commented 3 years ago

Got it & thank you!