Jump to content

Finding a route in mysql


unistake
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
Link to comment
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
  • Like 1
Link to comment
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
Link to comment
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 />';
}
?>
Link to comment
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);
Link to comment
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>';
}
?>
Link to comment
Share on other sites


-- 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 by unistake
Link to comment
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)
Link to comment
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.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.