[OSRM-talk] Route Optimizing
Hello, Are there any ambitions to create something like an optimization for route stops? And when not do you know any other way to do this via rest request? Jonas ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
Re: [OSRM-talk] Route Optimizing
You mean traveling salesman? Phil (trigpoint) On Mon Jul 6 14:36:33 2015 GMT+0100, Jonas Plass wrote: Hello, Are there any ambitions to create something like an optimization for route stops? And when not do you know any other way to do this via rest request? Jonas ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk -- Sent from my Jolla ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
Re: [OSRM-talk] Route Optimizing
Hi Jonas, Are there any ambitions to create something like an optimization for route stops? And when not do you know any other way to do this via rest request? If you are thinking of the TSP - https://en.wikipedia.org/wiki/Travelling_salesman_problem - then it is a simple problem of I need to visit X places after each other, please optimize the order to visit those places in. The solution is well-described in the WikiPedia link. You can write a little JavaScript, Python or whatever - and optimize on either distance or time. It is fairly simple, and all you use OSRM for is getting the costs. If you want as few calls to the OSRM-server as possible, then have a look at the table-service ( https://github.com/Project-OSRM/osrm-backend/wiki/Server-api#available-services ) Best regards, Greg Hans Gregers Petersen Partner, Seniorkonsulent greg...@septima.dk -- Septima P/S Frederiksberggade 28, 2. tv. 1459 København K www.septima.dk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
Re: [OSRM-talk] Route Optimizing
The OSRM team is working on a new API call to compute a round-trip that visits a list of point: https://github.com/Project-OSRM/osrm-backend/tree/feature/round_trip Med venlig hilsen Emil Tin IT- og Processpecialist Trafik ___ KØBENHAVNS KOMMUNE Teknik- og Miljøforvaltningen Byens Anvendelse Njalsgade 13, 1035 Postboks 380 2300 København S Direkte 2369 5986 Mobil 2369 5986 Email z...@tmf.kk.dk EAN 5798009493149 -Oprindelig meddelelse- Fra: Hans Gregers Petersen [mailto:greg...@septima.dk] Sendt: 6. juli 2015 15:55 Til: Mailing list to discuss Project OSRM Emne: Re: [OSRM-talk] Route Optimizing Hi Jonas, Are there any ambitions to create something like an optimization for route stops? And when not do you know any other way to do this via rest request? If you are thinking of the TSP - https://en.wikipedia.org/wiki/Travelling_salesman_problem - then it is a simple problem of I need to visit X places after each other, please optimize the order to visit those places in. The solution is well-described in the WikiPedia link. You can write a little JavaScript, Python or whatever - and optimize on either distance or time. It is fairly simple, and all you use OSRM for is getting the costs. If you want as few calls to the OSRM-server as possible, then have a look at the table-service ( https://github.com/Project-OSRM/osrm-backend/wiki/Server-api#available-services ) Best regards, Greg Hans Gregers Petersen Partner, Seniorkonsulent greg...@septima.dk -- Septima P/S Frederiksberggade 28, 2. tv. 1459 København K www.septima.dk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
Re: [OSRM-talk] Route Optimizing
Emil, See this for a good explanation of the various algorithms: http://www2.isye.gatech.edu/~mgoetsch/cali/VEHICLE/TSP/TSP003__.HTM Click the right arrow at the bottom of the page to see more algorithms. The heuristics for the traveling salesman problem fall into the following classes: Tour construction algorithms (creating an initial sub-tour and / or inserting remaining points if necessary) Tour improvement algorithms (improving the existing tour) Most of the time, a combination of algorithms from both of these classes is used. These are called composite procedures. The farthest insertion is a Tour construction algorithm and it could benefit from adding a simulated annealing of a tabu search optimizer to improve the initial tour construction. -Steve On 7/6/2015 4:16 PM, Emil Tin wrote: Seems it the farthest insertion algorithm although i'm not familiar with it. Sendt fra min iPhone Den 06/07/2015 kl. 21.40 skrev Stephen Woodbridge wood...@swoodbridge.com: I have not looked at the round_trip feature code, but if it is solving a TSP problem it really need to solve it for an asymmetric matrix and not a symmetric matrix. Most of the algorithms you find around the web solve the symmetric case, but because we are dealing with oneway streets and turn restrictions, etc there can be some big differences in cost based on the direction of travel between nodes. There is a way to convert an asymmetric matrix into a symmetric matrix that might be an option. Or if you are only looking for an approximate optimization solution then the symmetric matrix might be good enough. You can look at pgRouting and see what we have done there. -Steve On 7/6/2015 2:03 PM, Jonas Plass wrote: Thank you guys for the Inspiration. I will have a Look at it tomorrow. Am 06.07.2015 um 18:03 schrieb Stephen Woodbridge wood...@swoodbridge.com: A simple trick if you want to do start-via-via-...-via-end optimization like TSP is to use TSP and artificially set the distance between end and start locations to zero and this will keep those two city bound together. Then in the result just remove that link. This will allow the same code that solves TSP round trip to also optimize the vis points between a start and end trip. -Steve On 7/6/2015 10:02 AM, Emil Tin wrote: The OSRM team is working on a new API call to compute a round-trip that visits a list of point: https://github.com/Project-OSRM/osrm-backend/tree/feature/round_trip Med venlig hilsen Emil Tin IT- og Processpecialist Trafik ___ KØBENHAVNS KOMMUNE Teknik- og Miljøforvaltningen Byens Anvendelse Njalsgade 13, 1035 Postboks 380 2300 København S Direkte 2369 5986 Mobil 2369 5986 Email z...@tmf.kk.dk EAN 5798009493149 -Oprindelig meddelelse- Fra: Hans Gregers Petersen [mailto:greg...@septima.dk] Sendt: 6. juli 2015 15:55 Til: Mailing list to discuss Project OSRM Emne: Re: [OSRM-talk] Route Optimizing Hi Jonas, Are there any ambitions to create something like an optimization for route stops? And when not do you know any other way to do this via rest request? If you are thinking of the TSP - https://en.wikipedia.org/wiki/Travelling_salesman_problem - then it is a simple problem of I need to visit X places after each other, please optimize the order to visit those places in. The solution is well-described in the WikiPedia link. You can write a little JavaScript, Python or whatever - and optimize on either distance or time. It is fairly simple, and all you use OSRM for is getting the costs. If you want as few calls to the OSRM-server as possible, then have a look at the table-service ( https://github.com/Project-OSRM/osrm-backend/wiki/Server-api#available-services ) Best regards, Greg Hans Gregers Petersen Partner, Seniorkonsulent greg...@septima.dk -- Septima P/S Frederiksberggade 28, 2. tv. 1459 København K www.septima.dk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org
Re: [OSRM-talk] Route Optimizing
I have not looked at the round_trip feature code, but if it is solving a TSP problem it really need to solve it for an asymmetric matrix and not a symmetric matrix. Most of the algorithms you find around the web solve the symmetric case, but because we are dealing with oneway streets and turn restrictions, etc there can be some big differences in cost based on the direction of travel between nodes. There is a way to convert an asymmetric matrix into a symmetric matrix that might be an option. Or if you are only looking for an approximate optimization solution then the symmetric matrix might be good enough. You can look at pgRouting and see what we have done there. -Steve On 7/6/2015 2:03 PM, Jonas Plass wrote: Thank you guys for the Inspiration. I will have a Look at it tomorrow. Am 06.07.2015 um 18:03 schrieb Stephen Woodbridge wood...@swoodbridge.com: A simple trick if you want to do start-via-via-...-via-end optimization like TSP is to use TSP and artificially set the distance between end and start locations to zero and this will keep those two city bound together. Then in the result just remove that link. This will allow the same code that solves TSP round trip to also optimize the vis points between a start and end trip. -Steve On 7/6/2015 10:02 AM, Emil Tin wrote: The OSRM team is working on a new API call to compute a round-trip that visits a list of point: https://github.com/Project-OSRM/osrm-backend/tree/feature/round_trip Med venlig hilsen Emil Tin IT- og Processpecialist Trafik ___ KØBENHAVNS KOMMUNE Teknik- og Miljøforvaltningen Byens Anvendelse Njalsgade 13, 1035 Postboks 380 2300 København S Direkte 2369 5986 Mobil 2369 5986 Email z...@tmf.kk.dk EAN 5798009493149 -Oprindelig meddelelse- Fra: Hans Gregers Petersen [mailto:greg...@septima.dk] Sendt: 6. juli 2015 15:55 Til: Mailing list to discuss Project OSRM Emne: Re: [OSRM-talk] Route Optimizing Hi Jonas, Are there any ambitions to create something like an optimization for route stops? And when not do you know any other way to do this via rest request? If you are thinking of the TSP - https://en.wikipedia.org/wiki/Travelling_salesman_problem - then it is a simple problem of I need to visit X places after each other, please optimize the order to visit those places in. The solution is well-described in the WikiPedia link. You can write a little JavaScript, Python or whatever - and optimize on either distance or time. It is fairly simple, and all you use OSRM for is getting the costs. If you want as few calls to the OSRM-server as possible, then have a look at the table-service ( https://github.com/Project-OSRM/osrm-backend/wiki/Server-api#available-services ) Best regards, Greg Hans Gregers Petersen Partner, Seniorkonsulent greg...@septima.dk -- Septima P/S Frederiksberggade 28, 2. tv. 1459 København K www.septima.dk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
Re: [OSRM-talk] Route Optimizing
A simple trick if you want to do start-via-via-...-via-end optimization like TSP is to use TSP and artificially set the distance between end and start locations to zero and this will keep those two city bound together. Then in the result just remove that link. This will allow the same code that solves TSP round trip to also optimize the vis points between a start and end trip. -Steve On 7/6/2015 10:02 AM, Emil Tin wrote: The OSRM team is working on a new API call to compute a round-trip that visits a list of point: https://github.com/Project-OSRM/osrm-backend/tree/feature/round_trip Med venlig hilsen Emil Tin IT- og Processpecialist Trafik ___ KØBENHAVNS KOMMUNE Teknik- og Miljøforvaltningen Byens Anvendelse Njalsgade 13, 1035 Postboks 380 2300 København S Direkte 2369 5986 Mobil 2369 5986 Email z...@tmf.kk.dk EAN 5798009493149 -Oprindelig meddelelse- Fra: Hans Gregers Petersen [mailto:greg...@septima.dk] Sendt: 6. juli 2015 15:55 Til: Mailing list to discuss Project OSRM Emne: Re: [OSRM-talk] Route Optimizing Hi Jonas, Are there any ambitions to create something like an optimization for route stops? And when not do you know any other way to do this via rest request? If you are thinking of the TSP - https://en.wikipedia.org/wiki/Travelling_salesman_problem - then it is a simple problem of I need to visit X places after each other, please optimize the order to visit those places in. The solution is well-described in the WikiPedia link. You can write a little JavaScript, Python or whatever - and optimize on either distance or time. It is fairly simple, and all you use OSRM for is getting the costs. If you want as few calls to the OSRM-server as possible, then have a look at the table-service ( https://github.com/Project-OSRM/osrm-backend/wiki/Server-api#available-services ) Best regards, Greg Hans Gregers Petersen Partner, Seniorkonsulent greg...@septima.dk -- Septima P/S Frederiksberggade 28, 2. tv. 1459 København K www.septima.dk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
