Finding a route in mysql

unistake · November 24, 2015

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 November 24, 2015 by unistake

mac_gyver · November 24, 2015

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 November 24, 2015 by mac_gyver

Barand · November 25, 2015

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 November 25, 2015 by Barand

unistake · November 25, 2015

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 />';
}
?>

unistake · November 25, 2015

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

Edited November 25, 2015 by unistake

Barand · November 25, 2015

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);

unistake · November 25, 2015

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>';
}
?>

Barand · November 25, 2015

Can you post an sql dump of your rosters table?

unistake · November 25, 2015



-- phpMyAdmin SQL Dump

-- version 3.5.8.1

-- http://www.phpmyadmin.net

--

-- Host: website.com.mysql:3306

-- Generation Time: Nov 25, 2015 at 05:15 PM

-- Server version: 5.5.45-MariaDB-1~wheezy

-- 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,

  `AddedOn` datetime 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 November 25, 2015 by unistake

Barand · November 25, 2015

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".

unistake · November 25, 2015

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

Barand · November 25, 2015

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";

unistake · November 25, 2015

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

mac_gyver · November 25, 2015

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.

unistake · November 25, 2015

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

Works a treat.

Barand · November 25, 2015

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)

Sign In

Finding a route in mysql

Recommended Posts

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Join the conversation

Important Information