[pgrouting-users] Reg: Introduction to VRP Pickup and Delivery problem and work done in GSoC

[Manikanta Kondeti]

Hi all,

   I am Manikanta, a GSoC student for pgRouting. I've implemented a
partially optimized VRP-Pickup and Delivery Problem with time windows. This
algorithm has many practical uses in the real world. There is a big scope
to extend this problem and implement further.

   I thank my mentors Daniel and Steve for giving me this wonderful
opportunity and guiding me in the right way. Solving routing problems
became my passion and interest. Hence I'd love to contribute to pgRouting
in the future as well. This GSoC will be the first step. A lot more to
come.

*Repo details:*
https://github.com/pgRouting/pgrouting/tree/gsoc-vrppdtw/src/vrppdtw/src

*How to test it:*
  * Clone it from github
  * Compile and build it
         mkdir build && cd build
         cmake -DWITH_DD=ON ..
         make
         sudo make install
   * Open psql command line  (sudo su postgres)
          \c pgr_test__db__test     (Select Database)
          select * from pgr_gsoc_vrppdtw('select * from customer'::text,
25, 200);

* Output:*
   Output has 4 columns(seq, rid, nid, cost)
            seq:  starts from 0(first route first node) to (last route last
node)
              rid:  Shows the route id
              nid: Nodes in that particular route
            cost:  Cost calculated till that point

    Example:  *Sample output *
                     0 |   1 |   0 |    0
                     1 |   1 |  79 |  668
                     2 |   1 |  80 |  859
                     3 |   1 |  49 | 1091
                     4 |   1 |  47 | 1183
                     5 |   1 |   0 | 1201
                     6 |   2 |   0 |    0
                     7 |   2 |  81 |   47
                     8 |   2 |  76 |  293
                     9 |   2 |  70 |  477
                    10 |   2 |  73 |  570
                    11 |   2 |   0 |  625

*  Interpretation of this will be*:
     From seq 0 to 5 has details about first route and seq 6 to 11 about
second route.
       *Route 1*: Nodes->[0 79 80 49 47 0]  Cost -> [0  658 859  1091  1183
 1201]
       *Route 2:* Nodes->[0 81 76 70 73 0]  Cost -> [0 47 293 477 570 625]

       So final costs for route1 and route2 are 1201 and 625.

I'm planning to write a blog which contains all of these details. I'll do
it in a few weeks. Before that if you find any difficulties or want to give
me suggestions, feel free to contact me. Hope everything goes well.

Finally this is one of my best summers, thanks to my mentors & pgRouting
community. You're awesome :)

Thanks
Manikanta
LSI, IIIT-H
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20140826/d230a2d6/attachment.html>