Opened 7 years ago

Closed 5 years ago

#1177 closed feature request (done)

Integrate different VRP variants

Reported by: svonolfe Owned by: abeham
Priority: high Milestone: HeuristicLab 3.3.7
Component: Problems.VehicleRouting Version: 3.3.7
Keywords: Cc:

Description

Version 3.4 of the VRP should be implemented.

Features -> Multiple Variants of the VRP should be integrated (Single / Multi Depot, Homogenous / Heterogenous...)

Attachments (1)

VRP_design.pdf (7.8 KB) - added by svonolfe 5 years ago.
VRP Plugin Version 3.4 - Design

Download all attachments as: .zip

Change History (55)

comment:1 Changed 7 years ago by svonolfe

  • Status changed from new to accepted

comment:2 Changed 7 years ago by svonolfe

  • Version changed from 3.3 to 3.4

comment:3 Changed 7 years ago by svonolfe

Created branch in r4361

comment:4 Changed 7 years ago by svonolfe

Added initial version - WIP in r4362

comment:5 Changed 7 years ago by svonolfe

Worked on the evaluators and on the project structure of the VRP plugin - WIP in r4363

comment:6 Changed 7 years ago by svonolfe

Worked on VRP operators (WIP) in r4365

comment:7 Changed 7 years ago by svonolfe

Added move operators (WIP) in r4369

comment:8 Changed 7 years ago by svonolfe

Added move operators (WIP) in r4370

comment:9 Changed 7 years ago by svonolfe

Added analyzers and views in r4374

comment:10 Changed 7 years ago by svonolfe

Added Potvin encoding in r4376

comment:11 Changed 7 years ago by svonolfe

Improved performance of PotvinEncoding in r4378

comment:12 Changed 7 years ago by svonolfe

Added remaining encodings in r4379

comment:13 Changed 7 years ago by svonolfe

Improved moves, fixed behavior for SA in r4383

comment:14 Changed 7 years ago by svonolfe

Merged relevant changes from trunk into the branch in r4444

comment:15 Changed 7 years ago by svonolfe

Improved VRP evaluation in r4520

comment:16 Changed 7 years ago by abeham

  • Version changed from 3.4 to branch

comment:17 Changed 7 years ago by svonolfe

Merged relevant changes from the trunk into the branch (cloning,...) in r4752, fixed backwards compatibility in r4895

Last edited 7 years ago by svonolfe (previous) (diff)

comment:18 Changed 7 years ago by svonolfe

Implemented unified TS (WIP)in r5127

comment:19 Changed 7 years ago by abeham

  • Owner changed from svonolfe to abeham
  • Status changed from accepted to reviewing

I'll take this ticket and offer a review of the current code in the branch. We should start reintegrating this into the trunk some time next week and release this with the next iteration.

comment:20 Changed 7 years ago by svonolfe

Merged changes from trunk into branch in r5867, r6093

Last edited 6 years ago by svonolfe (previous) (diff)

comment:21 Changed 6 years ago by abeham

  • Priority changed from medium to high

comment:22 Changed 6 years ago by svonolfe

Merged changes from trunk (#1561) into branch in r6607, r6608

Last edited 6 years ago by svonolfe (previous) (diff)

comment:23 Changed 6 years ago by svonolfe

Added support for pickups and deliveries in r6710. Benchmark instances can be found at wiki:"Vehicle Routing Problem"?.

comment:24 Changed 6 years ago by svonolfe

Added adaptive constraint relaxation for all VRP variants in r6711

comment:25 Changed 6 years ago by svonolfe

Added biased multi operators for use with the SuccessfulOffspring analyzer in r6716

comment:26 Changed 6 years ago by svonolfe

Fixed minor bugs in VRP operators in r6751

comment:27 Changed 6 years ago by svonolfe

Added support for incremental evaluation to improve performance in r6752

comment:28 Changed 6 years ago by svonolfe

Added customer relocation manipulator in r6753

comment:29 Changed 6 years ago by svonolfe

Adapted creators to support pickup and delivery constraints in r6759

comment:30 Changed 6 years ago by svonolfe

Corrected behavior of various operators when a solution contains more tours than vehicles in r6771

comment:31 Changed 6 years ago by svonolfe

Added support for multiple moves in tabu search in r6772

comment:32 Changed 6 years ago by svonolfe

Added moves for pickup and delivery problems in r6773

comment:33 Changed 6 years ago by svonolfe

Minor changes:

  • Fixed possible race condition in moves in r6787
  • Fixed incorrect behavior of iterativeInsertionCreator for PD problems r6788
  • Added visualization of flows to PDP view in r6789

comment:34 Changed 6 years ago by svonolfe

Added support for multi depot CVRP instances in r6851

comment:35 Changed 6 years ago by svonolfe

Added support for the multi depot CVRP with time windows in r6854

Last edited 6 years ago by svonolfe (previous) (diff)

comment:36 Changed 6 years ago by svonolfe

Added support for the multi depot pickup and delivery problem with time windows in r6856

comment:37 Changed 6 years ago by svonolfe

Added vehicle assignment manipulator and move for multi depot instances in r6857

comment:38 Changed 6 years ago by svonolfe

Added pairwise manipulators, removed relocation manipulator in r6960

comment:39 Changed 6 years ago by svonolfe

Restructured VRP solution in r6970, r7088

Last edited 6 years ago by svonolfe (previous) (diff)

comment:40 Changed 6 years ago by gkronber

r7090: changed output paths for remaining targets (x86|x64|Any CPU (x) Debug|Release)

comment:41 Changed 6 years ago by svonolfe

Added static item image according to #1651 in r7203

comment:42 Changed 6 years ago by svonolfe

Added 2Opt* Movej in r7689

comment:43 Changed 5 years ago by svonolfe

Fixed some issues in the UTS in r7790, improved PDP moves in r7791

Changed 5 years ago by svonolfe

VRP Plugin Version 3.4 - Design

comment:44 Changed 5 years ago by svonolfe

Implemented review comments of abeham:

r7865 Fixed naming of moves (#1177)

r7864 Moved adaptive penalties to parameter values (#1177)

r7861 Fixed issues related to display of VRP solution (#1177)

r7859 Fixed issue in best solution analyzer (#1177)

r7858 Added color palette (#1177)

r7856 Fixed error in Prins and Zhu encodings (#1177)

r7855 Deactivated LS manipulators by default (#1177)

r7854 Adapted BestSolutionAnalyzer to dynamic constraint relaxation (#1177)

r7853 Added missing creators (#1177)

r7852 Moved parameters from the ProblemInstance to the Problem (#1177)

comment:45 Changed 5 years ago by svonolfe

Added VRP test instances in r7881, incorporated review comments of abeham in r7882, added additional test instances in r7883, added additional test instances in r7888, minor changes in r7884, r7887, r7891 and r7894

Last edited 5 years ago by svonolfe (previous) (diff)

comment:46 Changed 5 years ago by svonolfe

Trunk integration in r7895, r7896, r7897, r7898 and r7900

comment:47 Changed 5 years ago by svonolfe

Fixed issues that prevented the unit tests to pass in r7906

comment:48 Changed 5 years ago by mkommend

  • Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.7
  • Version changed from branch to 3.3.7

comment:49 Changed 5 years ago by ascheibe

r8003 adapted VRP branch to changes of r7999

comment:50 Changed 5 years ago by svonolfe

Derived VRP from Problem base class in r8006

comment:51 Changed 5 years ago by abeham

  • Owner changed from abeham to svonolfe
  • Status changed from reviewing to assigned

There is one final change that I suggest to make:

  • The text box displaying the routes in the "Tour" tab of the "Best VRP Solution" result should be set to be read-only. Currently it can be edited.

For the future:

  • There's currently just a very general VRPShakingOperator which uses all operators it can find. Maybe in future versions you can add specialized shaking operators that are working well out of the box. I understand that the user needs to know quite a lot on how to parameterize this operator in order to make effective use of e.g. VNS.

comment:52 Changed 5 years ago by svonolfe

  • Owner changed from svonolfe to abeham
  • Status changed from assigned to reviewing

Made tour text box in VRPSolutionView readonly in r8115. An efficient shaking operator for the VRP will be added in a later release.

comment:53 Changed 5 years ago by abeham

  • Status changed from reviewing to readytorelease

Thanks a lot.

comment:54 Changed 5 years ago by gkronber

  • Resolution set to done
  • Status changed from readytorelease to closed
Note: See TracTickets for help on using tickets.