# Finding a route in mysql

Go to solution Solved by Barand,

## Recommended Posts

Hi guys,

I am trying to make a quick code to find a route between two Place A and Place Z on 2015-11-23 that starts to leave after 6am.

Example table rows:

```DATE          DEPARTURE    LEAVE    ARRIVE     ARRIVAL
2015-11-23    Place A      04:00    Place Z    06:00    (this direct route leaves too early.)
2015-11-23    Place U      13:30    Place Z    14:20
2015-11-23    Place A      07:00    Place T    08:00
2015-11-23    Place A      09:00    Place U    12:00
2015-11-23    Place T      09:00    Place B    12:00
2015-11-23    Place B      13:00    Place Z    15:00

```

The output will show all routes available such as:

OPTION 1:
Place A to Place U (09:00-12:00)
**01:30 wait**
Place U to Place Z (13:30-14:20)

OPTION 2:
Place A to Place T (07:00-08:00)
**01:00 wait**
Place T to Place B (09:00-12:00)
**00:45 wait**
Place B to Place Z (12:45-15:00)

Thanks for the help

Edited by unistake
##### Share on other sites

here's one method -

1) take all the rows that have departure/arrival times between the earliest/latest departure/arrival time entered for the trip.

2) produce all possible combinations, taken 1 at a time, 2 at a time, .. up to the maximum number of segments you are willing to use in one trip (three would probably be a good maximum.)

3) throw out any routes that don't have an overall start and end point that matches the trip's start and end point and that don't have matching endings of one segment the same as the start of the next segment for all segments in the route.

4) for the remaining routes, calculate the layover time between each segment and the overall time of each route.

5) throw out any routes where any layover time between any segments is below a reasonable amount.

6) order the remaining routes by the number of segments, from least to most, and the overall time of each route, from least to most within the the same number of segments.

you may in fact be able to do this in an sql query. producing all the possible combinations, taken 1 at a time, 2 at a time, and 3 at a time, would (likely, just proposing this as a possibility) involve doing a UNION between  the single segments, the segments joined to themselves once, and the segments joined to themselves twice, with JOIN, WHERE, and HAVING conditions to only include rows in the result set that have the correct overall start and end points, matching segment-to-segment end/start points, and minimum layover times between segments.

Edited by mac_gyver
##### Share on other sites

Assuming no more than 2 changes en route

```mysql> select * from journey;
+----+------------+--------+----------+--------+----------+
| id | date       | depart | dep_time | arrive | arr_time |
+----+------------+--------+----------+--------+----------+
|  1 | 2015-11-23 | A      | 04:00:00 | Z      | 06:00:00 |
|  2 | 2015-11-23 | U      | 13:30:00 | Z      | 14:20:00 |
|  3 | 2015-11-23 | A      | 07:00:00 | T      | 08:00:00 |
|  4 | 2015-11-23 | A      | 09:00:00 | U      | 12:00:00 |
|  5 | 2015-11-23 | T      | 09:00:00 | B      | 12:00:00 |
|  6 | 2015-11-23 | B      | 13:00:00 | Z      | 15:00:00 |
+----+------------+--------+----------+--------+----------+

SELECT *
FROM (
SELECT depart as depA
, dep_time as deptimeA
, arrive as arrA
, arr_time as arrtimeA
FROM journey
WHERE depart='A' AND dep_time > '06:00'
) a
LEFT JOIN (
SELECT depart as depB
, dep_time as deptimeB
, arrive as arrB
, arr_time as arrtimeB
FROM journey
) b ON arrA = depB AND arrtimeA < deptimeB
LEFT JOIN (
SELECT depart as depC
, dep_time as deptimeC
, arrive as arrC
, arr_time as arrtimeC
FROM journey
WHERE arrive='Z'
) c ON arrB = depC AND arrtimeB < deptimeC;

+------+----------+------+----------+------+----------+------+----------+------+----------+------+----------+
| depA | deptimeA | arrA | arrtimeA | depB | deptimeB | arrB | arrtimeB | depC | deptimeC | arrC | arrtimeC |
+------+----------+------+----------+------+----------+------+----------+------+----------+------+----------+
| A    | 09:00:00 | U    | 12:00:00 | U    | 13:30:00 | Z    | 14:20:00 |      |          |      |          |
| A    | 07:00:00 | T    | 08:00:00 | T    | 09:00:00 | B    | 12:00:00 | B    | 13:00:00 | Z    | 15:00:00 |
+------+----------+------+----------+------+----------+------+----------+------+----------+------+----------+
```
Edited by Barand
##### Share on other sites

Thanks Barand!

Looks fantastic! Just I do not have enough experience to be able to use such a complex query.

I have tried to put it in to my own php but not sure where I am going wrong below..

```<?php
session_start();
include_once("cxn.inc");

// \$time = "00:01";
// \$today = "2015-11-26";
\$departure = "MAN";
\$destination = "DUB";

\$sql = "SELECT *
FROM (
SELECT Dep as depA
, BeginTime as deptimeA
, Arr as arrA
, EndTime as arrtimeA
FROM rosters
WHERE Dep='\$departure' AND BeginTime > '06:00'
) a
LEFT JOIN (
SELECT Dep as depB
, BeginTime as deptimeB
, Arr as arrB
, EndTime as arrtimeB
FROM journey
) b ON arrA = depB AND arrtimeA < deptimeB
LEFT JOIN (
SELECT depart as depC
, BeginTime as deptimeC
, Arr as arrC
, EndTime as arrtimeC
FROM journey
WHERE Arr='\$destination'
) c ON arrB = depC AND arrtimeB < deptimeC";

\$result = mysqli_query(\$cxn,\$sql)
or die ("Cant");

while(\$row=mysqli_fetch_assoc(\$result)) {
echo 'options<br />';
}
?>
```
##### Share on other sites

Whoops! Just noticed I didn't change the mysql table names above!

Edited by unistake
##### Share on other sites

Mk II version

```SELECT *
FROM (
SELECT depart as depA
, dep_time as deptimeA
, arrive as arrA
, arr_time as arrtimeA
FROM journey
WHERE depart='A' AND dep_time > '03:00'
) a
LEFT JOIN (
SELECT depart as depB
, dep_time as deptimeB
, arrive as arrB
, arr_time as arrtimeB
FROM journey
) b ON arrA = depB AND arrtimeA < deptimeB
LEFT JOIN (
SELECT depart as depC
, dep_time as deptimeC
, arrive as arrC
, arr_time as arrtimeC
FROM journey
) c ON arrB = depC AND arrtimeB < deptimeC
WHERE 'Z' IN (arrA, ArrB, ArrC);
```
##### Share on other sites

Thanks Barand,

Although now I can not return any values in the script below.

```<?php
session_start();
include_once("cxn.inc");

\$time = "03:00";
\$today = "2015-11-26";
\$departure = "A";
\$destination = "Z";

\$sql = "SELECT *
FROM (
SELECT Dep as depA
, BeginTime as deptimeA
, Arr as arrA
, EndTime as arrtimeA
FROM rosters
WHERE Dep='\$departure' AND BeginTime > '\$time' AND SectorDate = '\$today'
) a
LEFT JOIN (
SELECT Dep as depB
, BeginTime as deptimeB
, Arr as arrB
, EndTime as arrtimeB
FROM rosters
) b ON arrA = depB AND arrtimeA < deptimeB
LEFT JOIN (
SELECT Dep as depC
, BeginTime as deptimeC
, Arr as arrC
, EndTime as arrtimeC
FROM rosters
) c ON arrB = depC AND arrtimeB < deptimeC
WHERE '\$destination' IN (arrA, ArrB, ArrC);
";

\$result = mysqli_query(\$cxn,\$sql)
or die ("Cant");

while(\$row=mysqli_fetch_assoc(\$result)) {
foreach (\$row as \$key => \$value){
echo \$key.' - '.\$value.'<br />';
}
echo '<p> </p>';
}
?>
```
##### Share on other sites

Can you post an sql dump of your rosters table?

##### Share on other sites

```
-- version 3.5.8.1
--
-- Host: website.com.mysql:3306
-- Generation Time: Nov 25, 2015 at 05:15 PM
-- PHP Version: 5.3.3-7+squeeze15
SET SQL_MODE="NO_AUTO_VALUE_ON_ZERO";
SET time_zone = "+00:00";
/*!40101 SET @OLD_CHARACTER_SET_CLIENT=@@CHARACTER_SET_CLIENT */;
/*!40101 SET @OLD_CHARACTER_SET_RESULTS=@@CHARACTER_SET_RESULTS */;
/*!40101 SET @OLD_COLLATION_CONNECTION=@@COLLATION_CONNECTION */;
/*!40101 SET NAMES utf8 */;
--
-- Database: `website_com`
--
-- --------------------------------------------------------
--
-- Table structure for table `rosters`
--
CREATE TABLE IF NOT EXISTS `rosters` (
`RostersID` int(11) NOT NULL AUTO_INCREMENT,
`Code` varchar(7) NOT NULL,
`Ffname` varchar(60) NOT NULL,
`Fuid` varchar(100) NOT NULL,
`SectorDate` date NOT NULL,
`Duty` varchar(12) NOT NULL,
`Dep` varchar(10) NOT NULL,
`BeginTime` varchar(10) NOT NULL,
`EndTime` varchar(10) NOT NULL,
`Arr` varchar(10) NOT NULL,
`Random` int(4) NOT NULL,
PRIMARY KEY (`RostersID`)
) ENGINE=MyISAM  DEFAULT CHARSET=latin1 AUTO_INCREMENT=42 ;
--
-- Dumping data for table `rosters`
--
INSERT INTO `rosters` (`RostesID`, `Code`, `Ffname`, `Fuid`, `SectorDate`, `Duty`, `Dep`, `BeginTime`, `EndTime`, `Arr`, `AddedOn`, `Random`) VALUES
(1, 'TESTUSER', 'NAME', '102058860356986429', '2015-11-23', 'OFF(Z)', 'MAN', '00:00', '21:00', '', '2015-11-25 13:21:39', 272),
(2, 'TESTUSER', 'NAME', '102886039864529', '2015-11-24', 'OFF(Z)', 'MAN', '00:00', '21:00', '', '2015-11-25 13:21:39', 272),
(3, 'TESTUSER', 'NAME', '10065886039686429', '2015-11-25', 'OFF(Z)', 'MAN', '00:00', '21:00', '', '2015-11-25 13:21:39', 272),
(4, 'TESTUSER', 'NAME', '1025886039876429', '2015-11-26', '3246', 'MAN', '12:15', '14:10', 'STR\r', '2015-11-25 13:21:39', 272),
(5, 'TESTUSER', 'NAME', '10206539864276859', '2015-11-26', '3247', 'STR', '14:35', '16:30', 'MAN\r', '2015-11-25 13:21:39', 272),
(6, 'TESTUSER', 'NAME', '1020658839867887429', '2015-11-26', '1557', 'MAN', '17:30', '18:35', 'DUB\r', '2015-11-25 13:21:39', 272),
(7, 'TESTUSER', 'NAME', '10206588698678429', '2015-11-26', '1556', 'DUB', '19:00', '20:05', 'MAN\r', '2015-11-25 13:21:39', 272),
(8, 'TESTUSER', 'NAME', '1020658838768429', '2015-11-27', '1557', 'MAN', '17:30', '18:35', 'DUB\r', '2015-11-25 13:21:39', 272),
(9, 'TESTUSER', 'NAME', '10206588656873986429', '2015-11-27', '1556', 'DUB', '19:00', '20:05', 'MAN\r', '2015-11-25 13:21:39', 272),
(10, 'TESTUSER', 'NAME', '102065886873546986429', '2015-11-27', '4776', 'MAN', '20:30', '21:40', 'SNN\r', '2015-11-25 13:21:39', 272),
(11, 'TESTUSER', 'NAME', '1020658860768986566429', '2015-11-27', '4777', 'SNN', '22:05', '23:15', 'MAN\r', '2015-11-25 13:21:39', 272),
(12, 'TESTUSER', 'NAME', '1020658860376986429', '2015-11-28', 'SBY1030-Z', 'MAN', '11:45', '22:30', '', '2015-11-25 13:21:39', 272),
(13, 'TESTUSER', 'NAME', '102065886039675429', '2015-11-29', 'SBY1030-Z', 'MAN', '10:30', '22:30', '', '2015-11-25 13:21:39', 272),
(14, 'TESTUSER', 'NAME', '157658860398426759', '2015-11-30', '3187', 'MAN', '17:20', '20:00', 'MAD\r', '2015-11-25 13:21:39', 272),
(15, 'TESTUSER', 'NAME', '10206588603986429', '2015-11-30', '3186', 'MAD', '20:35', '23:15', 'MAN\r', '2015-11-25 13:21:39', 272),
(16, 'TESTUSER', 'NAME', '5464506567886036657986429', '2015-12-01', 'OFF(Z)', 'MAN', '00:00', '21:00', '', '2015-11-25 13:21:39', 272),
(17, 'TESTUSER', 'NAME', '10206587860653986429', '2015-12-02', 'OFF(Z)', 'MAN', '00:00', '21:00', '', '2015-11-25 13:21:39', 272),
(18, 'TESTUSER', 'NAME', '1020655567768603986429', '2015-12-03', 'OFF(Z)', 'MAN', '00:00', '21:00', '', '2015-11-25 13:21:39', 272),
(19, 'TESTUSER', 'NAME', '1020]88603986429', '2015-12-04', 'OFF(Z)', 'MAN', '00:00', '21:00', '', '2015-11-25 13:21:39', 272),
(20, 'TESTUSER', 'NAME', '10206588603984569', '2015-12-05', '4776', 'MAN', '06:55', '08:05', 'SNN\r', '2015-11-25 13:21:39', 272),
(21, 'TESTUSER', 'NAME', '16575472065886076867867', '2015-12-05', '4777', 'SNN', '08:30', '09:40', 'MAN\r', '2015-11-25 13:21:39', 272),
(22, 'TESTUSER', 'NAME', '1677765876429', '2015-12-05', '4096', 'MAN', '10:05', '12:45', 'RIX\r', '2015-11-25 13:21:39', 272),
(23, 'TESTUSER', 'NAME', '10206588603986429', '2015-12-05', '4097', 'RIX', '13:10', '16:05', 'MAN\r', '2015-11-25 13:21:39', 272),
(24, 'TESTUSER', 'NAME', '10206588603986429', '2015-12-06', '4007', 'MAN', '06:40', '09:30', 'ALC\r', '2015-11-25 13:21:39', 272),
(25, 'TESTUSER', 'NAME', '154674557429', '2015-12-07', 'SBY0400-Z', 'MAN', '04:00', '16:00', '', '2015-11-25 13:21:39', 272),
(27, 'TESTUSER', 'NAME', '102603986429', '2015-12-08', 'SBY0400-Z', 'MAN', '04:00', '16:00', '', '2015-11-25 13:21:39', 272),
(28, 'TESTUSER', 'NAME', '10240688606429', '2015-12-09', 'SBY0400-Z', 'MAN', '04:00', '16:00', '', '2015-11-25 13:21:40', 272),
(29, 'TESTUSER', 'NAME', '14354356658638429', '2015-12-10', 'OFF(Z)', 'MAN', '00:00', '21:00', '', '2015-11-25 13:21:40', 272),
(30, 'TESTUSER', 'NAME', '10206788603986429', '2015-12-11', 'OFF(Z)', 'MAN', '00:00', '21:00', '', '2015-11-25 13:21:40', 272),
(31, 'TESTUSER', 'NAME', '102686803986429', '2015-12-12', 'OFF(Z)', 'MAN', '00:00', '21:00', '', '2015-11-25 13:21:40', 272),
(32, 'TESTUSER', 'NAME', '10205888603986429', '2015-12-13', 'OFF(Z)', 'MAN', '00:00', '21:00', '', '2015-11-25 13:21:40', 272),
(33, 'TESTUSER', 'NAME', '102065603986429', '2015-12-14', '4332', 'MAN', '13:25', '18:00', 'TFS\r', '2015-11-25 13:21:40', 272),
(34, 'TESTUSER', 'NAME', '1020658689090903986429', '2015-12-14', '4331', 'TFS', '18:35', '23:10', 'MAN\r', '2015-11-25 13:21:40', 272),
(35, 'TESTUSER', 'NAME', '1020658886429', '2015-12-15', 'SBY1030-Z', 'MAN', '11:40', '22:30', '', '2015-11-25 13:21:40', 272),
(36, 'TESTUSER', 'NAME', '10206358893986429', '2015-12-16', 'SBY1030-Z', 'MAN', '10:30', '22:30', '', '2015-11-25 13:21:40', 272),
(37, 'TESTUSER', 'NAME', '1020658889986429', '2015-12-17', 'SBY1030-Z', 'MAN', '10:30', '22:30', '', '2015-11-25 13:21:40', 272),
(38, 'TESTUSER', 'NAME', '102063503986429', '2015-12-18', '4332', 'MAN', '13:25', '18:00', 'TFS\r', '2015-11-25 13:21:40', 272),
(39, 'TESTUSER', 'NAME', '1027860633588603986429', '2015-12-18', '4331', 'TFS', '18:35', '23:10', 'MAN\r', '2015-11-25 13:21:40', 272),
(40, 'TESTUSER', 'NAME', '10208868903986429', '2015-12-19', 'OFF(Z)', 'MAN', '00:00', '21:00', '', '2015-11-25 13:21:40', 272),
(41, 'TESTUSER', 'NAME', '102058889877603986429', '2015-12-20', 'OFF(Z)', 'MAN', '00:00', '21:00', '', '2015-11-25 13:21:40', 272);
/*!40101 SET CHARACTER_SET_CLIENT=@OLD_CHARACTER_SET_CLIENT */;
/*!40101 SET CHARACTER_SET_RESULTS=@OLD_CHARACTER_SET_RESULTS */;
/*!40101 SET COLLATION_CONNECTION=@OLD_COLLATION_CONNECTION */;```

Edited by unistake
##### Share on other sites

I was wondering if it was your airport roster table. There are not many departure and destination points in that table that have a value of "A" or "Z".

##### Share on other sites

I just used A - Z for a simple explanation of what I needed

##### Share on other sites

I just used A - Z for a simple explanation of what I needed

But you still use them in your code

\$time = "03:00";

\$today = "2015-11-26";

\$departure = "A";

\$destination = "Z";

##### Share on other sites

I replace them when I post on here for ease of reading. Still changing them for example to

\$departure = MAN

\$destination = DUB

It is not working

##### Share on other sites

most of your Arr column values are empty, and the ones that are not have a carriage-return \r appended to them and won't match what you are using as values in the php variable. you should remove the carriage-return from the database values.

##### Share on other sites

Barand thanks so much for your help! Mac_gyver you just finished it off

Works a treat.

##### Share on other sites

• Solution

Having seen your data reminded me you need to join on SectorDate too.

Mk III version

```SELECT *
FROM (
SELECT Dep as depA
, BeginTime as deptimeA
, Arr as arrA
, EndTime as arrtimeA
, SectorDate
FROM rosters
WHERE Dep='MAN' AND BeginTime > '03:00' AND SectorDate = '2015-11-26'
) a
LEFT JOIN (
SELECT Dep as depB
, BeginTime as deptimeB
, Arr as arrB
, EndTime as arrtimeB
, SectorDate
FROM rosters
) b ON arrA = depB AND arrtimeA < deptimeB AND a.SectorDate = b.SectorDate
LEFT JOIN (
SELECT Dep as depC
, BeginTime as deptimeC
, Arr as arrC
, EndTime as arrtimeC
, SectorDate
FROM rosters
) c ON arrB = depC AND arrtimeB < deptimeC AND b.SectorDate=c.SectorDate
WHERE 'DUB' IN (arrA, ArrB, ArrC)
```
##### Share on other sites

This thread is more than a year old. Please don't revive it unless you have something important to add.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Restore formatting

Only 75 emoji are allowed.