[pgrouting-dev] GSoC Proposal

Hi Mukul,

I have CC'd the dev list because these are good questions and others might have opinions also.

"user" is not defined so the problem is hard to answer. We have lots of users that have different requirements. For example:

A user of a web application? or a user of SQL?

We need to separate the data model from the presentation model. The presentation layer talks to someone like a web user. The SQL user expects data in table like structures and can easily be queried.

pgRouting in general is an engine that deals with solving problems that are primarily represented as tables of data.

So for most VRP like solvers we will have tables of data that get passed to the solver and the solver will return a set of records that look like a table.

So I could see a table of:

vehicles - to describe the vehicles capacity, efficiency, etc
orders - a list of orders to pickup or deliver, and their locations,
             and time windows if needed
depot - list of depots if not encoded in the order table.

Often we can represent depots in the order table with special ids or a flag.

Vehicles are assumed to be parked at the depot. But they could also have a "home" location associated with them that they leave and return to.

The results would be a set of records like:

seq, vehicle, depot, -1, depart - leave the depot
seq, vehicle, order, arrive, depart - pickup/deliver and order
seq, vehicle, depot, arrive, -1 - returns to the depot
<repeat for each vehicle>

Does this make sense?

Ask Daniel to forward to you the SmartVRP demo he built based on last years code.


On 3/13/2014 3:06 PM, Mukul priya wrote:

Hi ,

I have been reading a lot about TSP(asymmetric)and VRP (its different
versions) . I think the best implementable approach for both of them is
to follow the local search or tabu search.I have a few points that we
need to discuss.

1). it is important to implement vrp(any version) in such a way that a
user finds it easy to utse it and interpret the results. I would like
to discuss more about the structure that we can use to store the depot
information , vehicle information and cosutomer information .

2).Now if we think from users perspective these must be the input that
our procedure will need so some discussion on how we are going to fetch
these inputs form the user needs to be done .

3) As both of you mentioned we need to set some achievable goals and
then extend on that . So we will try to first achieve the basic solution
to VRP and then suppose we get lucky and have an optimized solution ,we
can then extend our goals .

      The other thing i wanted to ask was regarding two proposals on the
same topic (VRP) (even though the proposals will be on different
versions of it ) and questions might be raised by the osgeo committee
regarding it . So i wanted your suggestion whether i should make a
proposal on some different topic like Assymetric TSP ( It is almost the
same thing as VRP and It can also be solved using local search or 3-opt
or tabu search).The category of the problems is same so i won't have any
issue with that.


On Thu, Mar 13, 2014 at 6:42 AM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

    On 3/12/2014 9:04 PM, Daniel Kastl wrote:

        On Thu, Mar 13, 2014 at 7:44 AM, Manikanta Kondeti
        <mani.iiit123@gmail.com <mailto:mani.iiit123@gmail.com>
        <mailto:mani.iiit123@gmail.com>__>> wrote:

             Hi sir ,

             Thank you for fast and positive( :slight_smile: ) response.
             I have Mid-term exams till 15th starting from today. I am
             done with my proposal except the implementation part and
        also met
             mukul regarding the idea and proposal. I'm working on
        VRP-PDPTW. He
             is also working on other variation of VRP i.e... CVRP. I
        hope that
             won't be a problem ? . Will share the proposal with both
        you in less
             than 2 days.

        OK. That's good to hear.
        Just try to make your proposals distinguishable enough, so we don't
        later get asked why pgRouting needs another VRP algorithm.

        Also, like the Coursera seminar mentions, too, try to start with
        something more simple and improve the algorithm then step by step.
        With GSoC you always need to make sure, that there is a goal you can
        achieve even if something goes unexpectedly.
        So it's better to set some milestones, even some optional ones, like
        adding support for multiple depot or multiple capacities when
        there is time.

    Yes, this is VERY important. Students tend to be very optimistic and
    set grandiose goals. I like to see these are our minimum goals and
    these are our optional stretch goals if we have extra time.

    Coding the TABU search outside of of pgrouting is usually pretty
    easy, stuffing it into postgresql and debugging there always is
    harder than you think. Talk to Mukul about his experiences.

    We will help you set reasonable milestones for your projects if we
    have a chance to review them before the deadlines.



             Thanks ,

             On Thu, Mar 13, 2014 at 1:56 AM, Daniel Kastl

                 On Thu, Mar 13, 2014 at 5:18 AM, Stephen Woodbridge
        <mailto:woodbri@swoodbridge.com>>> wrote:

                     Hi Manikanta,

                     Daniel is fine with you going forward with the PDPTW
                     proposal. He was just asking how it is different
        from the
                     DARP code we already have because he is not
        familiar with
                     the details of the various problems and solution.

                     Anyway, You are fine proceeding with your plan.


                 Hi Manikanta,

                 Steve is right.
                 I just asked about the differences, because I had no
        time to
                 read the paper in details :wink:
                 It's probably a good idea, if you make sure that you
        and Mukul
                 don't submit something that is too similar.


                 Georepublic UG (haftungsbeschränkt)
                 Salzmannstraße 44,
                 81739 München, Germany

                 eMail: daniel.kastl@georepublic.de
                 Web: http://georepublic.info

                 Tel: +49 (089) 4161 7698-1
                 Fax: +49 (089) 4161 7698-9

                 Commercial register: Amtsgericht München, HRB 181428
                 CEO: Daniel Kastl

        Georepublic UG (haftungsbeschränkt)
        Salzmannstraße 44,
        81739 München, Germany

        eMail: daniel.kastl@georepublic.de
        Web: http://georepublic.info

        Tel: +49 (089) 4161 7698-1
        Fax: +49 (089) 4161 7698-9

        Commercial register: Amtsgericht München, HRB 181428
        CEO: Daniel Kastl