Changes between Initial Version and Version 1 of Documentation/Howto/ImplementANewVRPEncoding


Ignore:
Timestamp:
02/20/14 10:25:59 (6 years ago)
Author:
pfleck
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Documentation/Howto/ImplementANewVRPEncoding

    v1 v1  
     1work in progress ...
     2
     3= How to ... implement a new VRPEncoding =
     4
     5== Goals ==
     6
     7One way to implement a new VRP variant is by implementing a new {{{VRPEncoding}}} and new {{{Operators}}}. This is a suitable possibility if the VRP variant requires additional decision variables to optimize. Based on these new decision variables, new {{{Operators}}} for ''crossing'' and ''mutating'' solutions in the search process of algorithms (e.g. a ''Genetic Algorithm'') are required.
     8
     9
     10A {{{VRPEncoding}}} is the representation of a solution candidate for a given {{{ProblemInstance}}} (see [wiki:UsersHowtosImplementANewVRPProblemInstance How to ... implement a new VRP ProblemInstance]). There are different ways of representing and operating on tours of a VRP solution. ([http://link.springer.com/chapter/10.1007%2F978-3-642-27549-4_42 source]) Different {{{Encodings}}} require different {{{Operators}}} to work on. This way of extending the vehicle routing problem allows you to modify the search process and yielding results with additinal decition variables.
     11
     12After this tutorial you will be able to implement you own VRP variants that require additional decision variables. You will also have a basic understanding of the concepts and architecture concerning the {{{VRPEncoding}}}, the {{{VRPOperator}}} concepts and related components.
     13
     14== The Multi Trip Vehicle Routing Problem ==
     15
     16To show the procedure of implementing a new {{{VRPEncoding}}}, the implementation of the ''Multi Trip Vehicle Routing Problem  (MTVRP)'' ([http://www.jstor.org/discover/10.2307/3009960?uid=3737528&uid=2&uid=4&sid=21103529629063 source]) is demonstrated. The MTVRP allows vehicles to return to the depot, refill their cargo and therefore can satisfy multiple tours. In addition the maximum driving distance of each vehicle is limited. Usually MTVRP solutions require much fewer vehicles compared to standard VRP variants because a vehicle can drive multiple tours.
     17
     18In this tutorial, the MTVRP is based on the {{{Capacitated Vehicle Routing Problem (CVRP)}}}. In addition we have to specify the maximum distance a vehicle can drive as well the penalty for exceeding the maximum distance.
     19
     20To implement the new {{{Encoding}}} we extend the existing {{{PotvingEncoding}}} ([http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.8719 source]). In addition, the available operators for the {{{PotvinEncoding}}} will be extended in order to make use of the new data in the encoding. The advantage of extending an existing encoding is that we can reuse the original operators in the algorithm. If you like to implement a complete new encoding you also have to implement all operators yourself.
     21
     22== Prerequisites ==
     23
     24Before you start, make sure you have the latest version of the HeuristicLab source code ready. Then create a new plugin called {{{HeuristicLab.MultiTripVRP}}}. For additional help for creating a new plugin, see [wiki:UsersHowtosImplementPluginsStepByStep How to ... create HeuristicLab plugins (step by step)].
     25
     26Your plugin need an additional dependency onto the {{{HeuristicLab.Problems.VehicleRouting}}} plugin. The plugin should look like this:
     27
     28{{{
     29#!cs
     30[Plugin("HeuristicLab.MultiTripVRP", "1.0.0.0")]
     31[PluginFile("HeuristicLab.MultiTripVRP.dll", PluginFileType.Assembly)]
     32[PluginDependency("HeuristicLab.Problems.VehicleRouting", "3.4")]
     33public class MultiTripVRPPlugin : PluginBase {
     34}
     35}}}
     36
     37In addition you will need references onto following HeuristicLab assemblies:
     38 - HeuristicLab.Collections
     39 - HeuristicLab.Common
     40 - HeuristicLab.Core
     41 - HeuristicLab.Data
     42 - HeuristicLab.Encodings.PermutationEncoding
     43 - HeuristicLab.Operators
     44 - HeuristicLab.Optimization
     45 - HeuristicLab.Parameters
     46 - HeuristicLab.Persistence
     47 - '''HeuristicLab.Problems.VehicleRouting'''
     48
     49= Implementing new Encoding =
     50
     51= Sample Foundations =
     52== MultiTripVRPInstance ==
     53== MultiTripEvaluator ==
     54
     55= Implementing new Operators =
     56== Foundations ==
     57== Link Encoding/Operators to VRP variants ==
     58== Implementing new MultiTripOperator ==
     59== Implementing new Creator ==
     60== Implementing new Manipulator ==
     61== Implement new Crossover ==
     62
     63= Result =
     64== Configure Algorithm ==
     65== Interpretation ==