Loading ...
Sorry, an error occurred while loading the content.

342Re: [aima-talk] Re: Project ideas!

Expand Messages
  • seA
    Mar 17, 2004
    • 0 Attachment
      can i represent this VRP as a Reinforcement Learning problem? becaus im thinking about using RL for my mini project,any idea?

      ���� <chenyu468@...> wrote:
      Yes, ��Vehicle route problem�� is a search problem. It is a central
      problem in distribution management. The classical problem��s
      description is:
      1.      brief:
      a)      One company has many customers for distribution products.
      The company has many vehicles fore doing the work. Every customer��s
      order is small. Company wants to design a plan for all vehicles to
      lower the distribution cost.
      2.      details:
      a)      G = (V,E) be an undirected graph where V = {v0,v1,�­vn} is
      a set of vertices representing customers. E ={(vi,vj)|vi,vj belong to
      V, i<j} is the edge set.
      b)      Vertex v0 denotes a depot at which are based m identical
      vehicles of capacity Q, where m is a decision variable or a constant.
      c)      Each customer of V\{v} has a non-negative demand qi, a non-
      negative service time si. (waiting, unloading time)
      d)      A distance matrix (cij) is defined on E. We use the terms
      distance and travel time interchangeably.
      Problem(VRP---for vehicle route problem
      1.      designing a set of m vehicles routes having a minimum total
      length and such that
      a)      each route start and ends at the depot
      b)      each remaining city is visited exactly once by one vehicle
      c)      the total demand of a route does not exceed
      d)      The total duration of a route does not exceed a preset
      limit L.

      Many people think that the core of VRP is TSP (traveling salesman
      problem). But it is more difficult than TSP. TSP has only one

      Many variants of VRP exists,
      1.      To delete the above fact b. Some customer��s order is very
      big so that the order is more than the vehicle��s capacity.
      2.      Another special vertex appears. It is not customer. It is
      highway fee collection point. Therefore the Problem-1 requirement
      should be modified.
      3.      Many different kind of vehicle exists, For example, one
      kind of vehicles are for freezing products, one kind of vehicles are
      for common products.
      4.      Every vehicle can have more than 1 route.
      5.      etc.

      There are many different approachs to solve the problem:
      1.      hill climbing
      2.      simulated annealing
      3.      neural network
      4.      GA
      5.      ant system
      6.      etc

      I think many knowledge of AIMA can be applied to this problem, and
      this problem��s requirement is easy to imagine and new requirement
      can be added for more difficulty.

      Thank you for your attention.
      Best regards/chenyu (shanghai, China)


      Do you Yahoo!?
      Yahoo! Mail - More reliable, more storage, less spam

    • Show all 12 messages in this topic